歡迎跟着夏老師一起學習算法。
關注公衆号可以進行交流和加入微信群，群内定期有系列文章分享噢！
Question
給定一個字元串，請你找出其中不含有重複字元的 最長子串 的長度。
示例1：
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重複字元的最長子串是 "abc"，是以其長度為 3。
示例2：
輸入: "bbbbb"
輸出: 1
解釋: 因為無重複字元的最長子串是 "b"，是以其長度為 1。
示例3：
輸入: "pwwkew"
輸出: 3
解釋: 因為無重複字元的最長子串是 "wke"，是以其長度為 3。
請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。
周遊法
最容易想到的一種算法，也是效率最低的一種算法
- 通過兩次周遊得到所有可能的 子字元串 清單
- 将每個字元串傳入一個函數檢測是否包含重複字元，如果不包含則更新最長子串的長度
// 判斷給定的子串是否包含重複字元
function isUnique(str, start, end) {
const chars = [];
for(let i = start; i < end; i++) {
const char = str[i];
if(chars.indexOf(char) !== -1) { // 字元已存在，本字元串不符合條件
return false;
}
chars.push(char); // 添加字元
}
return true;
}
// 擷取字元串最長子串長度
function lengthOfLongestSubstring(s) {
let max = 0;
for(let i = 0; i < s.length; i++) {
for(let j = i+1; j <= s.length; j++) {
if(isUnique(s, i, j)) { // 判斷子串是否唯一
max = Math.max(max, j - i); // j - i 為目前子串長度
}
}
}
return max;
}
時間複雜度$O(n^3)$
i循環，j循環，isUnquie中的循環，3次循環嵌套
空間複雜度$O(min(n,m))$
isUnique函數中定義了一個數組來存儲不重複的子串字元，長度為$k$,$k$的長度取決于字元串$s$的大小$n$以及 字元串$s$包含的不重複字元數大小$m$
滑動視窗法
暴力法中我們會重複檢查一個子串是否包含重複的字元，如果從$i$ ~ $j-1$ 之間的子串已經被檢查過沒有重複字元了，那麼隻需要檢查$s[j]$是否在這個子串就行了。
子串使用js自帶的資料結構Set存儲
如果不在該子串，那麼子串長度+1，$j+1$，繼續往後走
如果在這個子串，證明出現了重複，我們需要将$s[i]$移出來之後$i+1$，繼續往後走
function lengthOfLongestSubstring(s) {
const set = new Set();
const max = 0;
let i = 0;
let j = 0;
while(i < s.length && j < s.length) {
if(!set.has(s[j])) { // j 不在set中，set中添加s[j],j後移，同時更新最大子串長度
set.add(s[j]);
j++;
max = Math.max(max, j - i);
} else {
set.delete(s[i]); // 移除set左邊的資料，i後移一位
i++;
}
}
return max;
}
時間複雜度 $O(2n) \approx O(n)$
最好的情況是j一次走完沒有出現重複，最壞的情況是i和j都走到了末尾
```
時間複雜度 $O(n)$
隻周遊了j
空間複雜度 $O(min(n,m))$
與之前的方法相同
Q: 為什麼第8行的 i = Math.max(i, map[char]) 不能直接是 i = map[char]?
A: $i$ 的位置比map[char]大的情況下如果直接指派會導緻 $i$ 往前面走，會導緻傳回的子串長度大于實際的子串長度
錯誤例子 abba
可以看到第4次循環中 i 的位置已經出現了問題，把位置1的a拿過來進行計算了，視窗的起始左邊也從2變成了1，往回走了。 ![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)