給定一個字符串，請你找出其中不含有重復字符的 最長子串 的長度。
示例 1：
輸入: s = "abcabcbb"
輸出: 3
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。
示例 2:
輸入: s = "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1。
示例 3:
輸入: s = "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3。
請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。
示例 4:
輸入: s = ""
輸出: 0
數(shù)據(jù)范圍：
0 <= s.length <= 5 * 10^4-
s由英文字母、數(shù)字、符號和空格組成
暴力解法
這道問題的暴力解法是：
- 枚舉所有的子串，
；
- 再對每一個子串，再對每一個子串判斷是否有重復字符
；
因此總的時間復雜度為 。
暴力解法的優(yōu)化
注意到這樣的事實：
- 如果一個子串包含重復字符，那么與它有相同左端點的、長度更長的字符串一定也包含重復字符；
- 又由于題目只要求我們找最長不重復子串的 長度（只要求返回長度，不要求得到具體的子串的結(jié)果），如果已經(jīng)找到了一個長度為
的子串，那么小于等于長度
基于這兩點，我們就可以使用 右指針左指針交替向右移動的方式 考慮完所有暴力解法需要考慮的子串，也就是說「滑動窗口」的解法實現(xiàn)了「剪枝」的效果。
這里請大家在腦海里想象一下，實在在腦海里想不太明白的話，在草稿紙上做一些簡單的計算就非常清楚了。
暴力解法我們需要考慮所有可能的子串，我們把它們列出表格如下。我么用數(shù)對 表示子串
s[i..j] 。
而使用滑動窗口算法我們需要考慮的子串如下圖所示。
可以看出，滑動窗口算法只要右指針移動到數(shù)組的末尾程序就結(jié)束了。暴力解法需要考慮的子串的數(shù)量級是 （具體我們就不計算它了），而滑動窗口我們需要考慮的子串為
（我沒有寫得很具體，相信大家能明白我的意思）。
還需要解決的一個問題，如何判斷子串里是否有重復的字符，很容易想到使用「哈希表」統(tǒng)計字符出現(xiàn)次數(shù)。注意到題目的「數(shù)據(jù)范圍」里說到：s 由英文字母、數(shù)字、符號和空格組成。我們還可以使用數(shù)組代替哈希表，事實上哈希表的底層也是數(shù)組。
- 當右指針向右移動將字符納入滑動窗口的時候，字符的頻數(shù)加 1；
- 當左指針向右移動將字符移出滑動窗口的時候，字符的頻數(shù)減 1。
其它細節(jié)我們就不贅述了。請見「參考代碼」：
public class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
if (len < 2) {
return len;
}
// 當 window 中某個字符的頻數(shù)為 2 時，表示滑動窗口內(nèi)有重復字符
// 頻數(shù)數(shù)組，128 由測試數(shù)據(jù)的范圍決定
int[] freq = new int[128];
// 轉(zhuǎn)換為字符數(shù)組，避免每一次 s.charAt() 方法檢查下標越界
char[] charArray = s.toCharArray();
int left = 0;
int right = 0;
int res = 1;
// 循環(huán)不變量：區(qū)間[left..right] 內(nèi)沒有重復元素
while (right < len) {
freq[charArray[right]]++;
// 此時 [left..right) 內(nèi)如果沒有重復元素，就嘗試擴張 right
// 否則縮小左邊界，while 循環(huán)體內(nèi)不斷縮小邊界
if (freq[charArray[right]] == 2) {
while (freq[charArray[right]] == 2) {
freq[charArray[left]]--;
left++;
}
}
// 此時 [left..right] 內(nèi)沒有重復元素
res = Math.max(res, right - left + 1);
right++;
}
return res;
}
}
時間復雜度：右指針遍歷了數(shù)組一次、左指針還沒有遍歷到數(shù)組的末尾就停了下來，因此時間復雜度為 。
本題小結(jié)：
滑動窗口的問題基本上都可以寫成「雙重循環(huán)」的樣子，其中：
- 外層循環(huán)讓右指針向右移動；
- 內(nèi)層循環(huán)讓左指針向右移動。
在「力扣」的題解區(qū)有很多大佬提供了代碼的模板，但是我們在這里建議大家通過練習去理解每一行代碼的意思，不同的問題具體細節(jié)不一樣，不可以生搬硬套。
歡迎大家關(guān)注我的公眾號「算法不好玩」，B 站搜索「liweiwei1419」，我講解的算法知識特別好懂。
