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