題目：給定一個字符串，請你找出其中不含有重復(fù)字符的最長子串的長度栓始。
示例1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "abc"，所以其長度為 3。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因為無重復(fù)字符的最長子串是 "b"贝攒，所以其長度為 1。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是"wke"时甚，所以其長度為 3隘弊。
請注意，你的答案必須是 子串 的長度荒适，"pwke"是一個子序列梨熙，不是子串。
算法思路：
- 暴力法：逐個檢查所有的子字符串刀诬，看它是否不含有重復(fù)的字符咽扇；算法復(fù)雜度0(n^2)；
- 借助隊列先進先出的屬性：遍歷字符串的同時判斷當前字符是否包含在前面遍歷的子字符串中舅列，若存在則依次把隊列中的字符串“出列”肌割，直到與當前遍歷到的字符相同的字符“出列”為止；若不存在則字符串長度加1帐要，繼續(xù)遍歷把敞。每次遍歷的時候要比較記錄的最大長度和每個子串的長度，取最大值賦值給最大長度榨惠；利用這種思路實現(xiàn)的算法效率不是很高奋早，在leecode官網(wǎng)提交的算法代碼執(zhí)行時間是8ms；
- 滑動窗口：借助隊列實現(xiàn)起來比較簡單赠橙，但增加了創(chuàng)建隊列和遍歷隊列的開銷耽装，可以借鑒隊列的核心原理實現(xiàn)：只需要記錄子串在父串中的索引位置，不借助隊列期揪，也不新建字符串掉奄，防止增加額外的開銷。利用這種思路實現(xiàn)的算法效率比較高凤薛，在leecode官網(wǎng)提交的算法代碼執(zhí)行時間是3ms姓建；
算法代碼：暴力法的代碼比較簡單，就不寫代碼了缤苫，感興趣的可以自己實現(xiàn)一下速兔。
算法代碼：根據(jù)算法思路2，寫出的算法具體代碼如下：
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int max = 0;
int curMax = 0;
ArrayDeque<Character> queue = new ArrayDeque<>();
for (int i = 0; i < s.length(); i ++) {
char curChar = s.charAt(i);
if (!queue.contains(s.charAt(i))) {
queue.add(curChar);
curMax ++;
} else {
if (curMax > max) {
max = curMax;
}
char c = queue.remove();
curMax --;
while (c != curChar) {
c = queue.remove();
curMax --;
}
queue.add(curChar);
curMax ++;
}
}
if (curMax > max) {
max = curMax;
}
return max;
}
算法代碼：根據(jù)算法思路3活玲，寫出的算法具體代碼如下：
public int lengthOfLongestSubstring(String s) {
int max = 0; // 最長子串的長度
int curMax = 0; // 記錄當前遍歷的子串長度
int index = 0; // 記錄已遍歷的重復(fù)元素的位置
char curChar;
boolean contain = false;
for (int i = 0; i < s.length(); i ++) {
curChar = s.charAt(i);
int j;
for (j = index; j < i; j ++) {
if (s.charAt(j) == curChar) {
contain = true;
break;
}
}
if (!contain) {
curMax ++;
if (curMax > max) {
max = curMax;
}
} else {
curMax = i - j;
index = j + 1;
contain = false;
}
}
return max;
}
??如果你有疑問或更好的算法思路涣狗，歡迎留言交流５瘛！镀钓！
??如果感覺我的文章對您有所幫助穗熬，麻煩動動小手給個喜歡，謝謝６〗ΑＫ缆健！
