給定一個字符串，請你找出其中不含有重復(fù)字符的 最長子串 的長度。
示例 1:
輸入: s = "abcabcbb"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "abc"仆救，所以其長度為 3。
示例 2:
輸入: s = "bbbbb"
輸出: 1
解釋: 因為無重復(fù)字符的最長子串是 "b"，所以其長度為 1其骄。
示例 3:
輸入: s = "pwwkew"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "wke"，所以其長度為 3扯旷。
請注意拯爽，你的答案必須是 子串 的長度，"pwke" 是一個子序列钧忽，不是子串毯炮。
示例 4:
輸入: s = ""
輸出: 0
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)耸黑，非商業(yè)轉(zhuǎn)載請注明出處桃煎。
思路一：
不用動腦筋的方法，仍然是一個雙重循環(huán)遍歷大刊。從字符串的第一位開始备禀，一個個往后找最長不重復(fù)的子串，取長度最大的
例如‘pwwkew’
- 從第0位開始看，p往后找到不重復(fù)子串為pw曲尸，長度為2
- 第1位w往后不重復(fù)子串只有w赋续，長度為1
- 第2位w往后不重復(fù)子串是wke, 長度為3
- 第3位k往后不重復(fù)子串是kew, 長度為3
- 第4位e往后不重復(fù)子串是ew，長度為2
- 最后一位w不重復(fù)子串是w另患，長度為1
- 因此我們得到結(jié)果是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往前的任意字符開始到當(dāng)前位置，都會出現(xiàn)兩個重復(fù)的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)全部遍歷完成，無重復(fù)字符的最長子串長度為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;
};
