給定一個字符串，請你找出其中不含有重復字符的 最長子串 的長度。
示例 1:
輸入: s = "abcabcbb"
輸出: 3
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。
示例 2:
輸入: s = "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1。
示例 3:
輸入: s = "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3。
請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。
示例 4:
輸入: s = ""
輸出: 0
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作權歸領扣網(wǎng)絡所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權，非商業(yè)轉(zhuǎn)載請注明出處。
思路一：
不用動腦筋的方法，仍然是一個雙重循環(huán)遍歷。從字符串的第一位開始，一個個往后找最長不重復的子串，取長度最大的
例如‘pwwkew’
- 從第0位開始看，p往后找到不重復子串為pw，長度為2
- 第1位w往后不重復子串只有w，長度為1
- 第2位w往后不重復子串是wke, 長度為3
- 第3位k往后不重復子串是kew, 長度為3
- 第4位e往后不重復子串是ew，長度為2
- 最后一位w不重復子串是w，長度為1
- 因此我們得到結果是3
代碼實現(xiàn)
var lengthOfLongestSubstring = function(s) {
let max = 0;
for(let i = 0; i<s.length; i+=1) {
let temp = [s[i]];
for(let j = i+1; j<s.length; j+=1) {
if (temp.includes(s[j])) {
break;
}
temp.push(s[j]);
}
max = Math.max(max, temp.length);
}
return max;
};
思路二：
我們用滑動窗口的思想來解決。什么是滑動窗口呢? 我們直接來看這個例子，用例子來說明
例如‘pwwkew’
- 我們先建立一個空窗口，用一個數(shù)組來表示windowArr = []
- 遍歷字符串，字符串的第0位p在窗口中不存在，我們把它加進去, windowArr = ['p']， 此時最大子串長度為1
- 字符串的第1位w在窗口中不存在，我們把它加進去, windowArr = ['p', 'w']， 此時最大子串長度為2
- 字符串的第2位w在窗口中已經(jīng)存在了，出現(xiàn)的位置為1，也就是說從位置1往前的任意字符開始到當前位置，都會出現(xiàn)兩個重復的w，那位置1之前的所有字符我們都不需要再考慮了，直接把窗口滑到位置1之后，也就是位置2， windowArr = ['w'],此時最大子串長度還是為2
- 字符串的第3位k在窗口中不存在，我們把它加進去，windowArr = ['w', 'k'], 此時最大子串長度為2
- 字符串的第4位e在窗口中不存在，我們把它加進去，windowArr = ['w', 'k', 'e'], 此時最大子串長度為3
- 字符串的第5位w在窗口中已經(jīng)存在了，出現(xiàn)的位置是0，所以我們把窗口滑到0之后，也就是['k','e', 'w'], 此時最大子串長度為3
字符串已經(jīng)全部遍歷完成，無重復字符的最長子串長度為3
滑動窗口示例
代碼實現(xiàn)
var lengthOfLongestSubstring = function(s) {
let windowArr = [];
let max = 0;
for(let i = 0; i<s.length; i+=1) {
const existedIndex = windowArr.indexOf(s[i]);
if (existedIndex > -1) {
windowArr.splice(0, existedIndex +1);
}
windowArr.push(s[i]);
max = Math.max(max, windowArr.length);
}
return max;
};
