給定一個字符串，請你找出其中不含有重復字符的 最長子串 的長度。
示例 1:
輸入: "abcabcbb" 輸出: 3 解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。
示例 2:
輸入: "bbbbb" 輸出: 1 解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1。
示例 3:
輸入: "pwwkew" 輸出: 3 解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3。
請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。
方法一：滑動窗口
思路和算法
我們先用一個例子來想一想如何在較優的時間復雜度內通過本題。
我們不妨以示例一中的字符串abcabcbb為例，找出從每一個字符開始的，不包含重復字符的最長子串，那么其中最長的那個字符串即為答案。對于示例一中的字符串，我們列舉出這些結果，其中括號中表示選中的字符以及最長的字符串。
-
以 (a)bcabcbb開始的最長字符串為 (abc)abcbb；
-
以 a(b)cabcbb開始的最長字符串為 a(bca)bcbb；
-
以 ab(c)abcbb開始的最長字符串為 ab(cab)cbb；
-
以 abc(a)bcbb開始的最長字符串為 abc(abc)bb；
-
以 abca(b)cbb開始的最長字符串為 abca(bc)bb；
-
以 abcab(c)bb開始的最長字符串為 abcab(cb)b；
-
以 abcabc(b)b開始的最長字符串為 abcabc(b)b；
-
以 abcabcb(b)開始的最長字符串為 abcabcb(b)。
發現了什么？如果我們依次遞增地枚舉子串的起始位置，那么子串的結束位置也是遞增的！這里的原因在于，假設我們選擇字符串中的第K個字符作為起始位置，并且得到了不包含重復字符的最長子串的結束位置為rk。那么當我們選擇第k+1個字符作為起始位置時，首先從k+1到rk的字符顯然是不重復的，并且由于少了原本的第k個字符，我們可以嘗試繼續增大rk，直到右側出現了重復字符為止。
這樣以來，我們就可以使用[滑動窗口來解決這個問題了：
-
我們使用兩個指針表示字符串的某個子串(的左右邊界)。其中左指針代表著上文中[枚舉子串的其實位置]，而右指針即為上文中rk；
-
在每一步的操作中，我們會將左指針向右移動一格，表示我們開始枚舉下一個字符作為起始位置，然后我們可以不斷地向有移動有指針，但需要保證這兩個指針對應的子串中沒有重復的字符。在移動結束后，這個子串就對應著以左指針開始的，不包含重復字符的最長子串。我們記錄下這個子串的長度；
-
在枚舉結束后，我們找到的最長的子串的長度即為答案。
判斷重復字符
在上面的流程中，我們還需要使用一種數據結構來判斷是否有重復的字符，常用的數據結構為哈希集合(即Java中的HashSet)。在左指針向右移動的時候，我們從哈希集合中移動一個字符，在有指針向右移動的時候，我們網哈希集合中添加一個字符。
至此，我們就完美解決了本題。
class Solution {
public int lengthOfLongestSubstring(String s) {
// 哈希集合，記錄每個字符是否出現過
Set<Character> occ = new HashSet<Character>();
int n = s.length();
// 右指針，初始值為 -1，相當于我們在字符串的左邊界的左側，還沒有開始移動
int rk = -1, ans = 0;
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指針向右移動一格，移除一個字符
occ.remove(s.charAt(i - 1));
}
while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
// 不斷地移動右指針
occ.add(s.charAt(rk + 1));
++rk;
}
// 第 i 到 rk 個字符是一個極長的無重復字符子串
ans = Math.max(ans, rk - i + 1);
}
return ans;
}
}
作者：LeetCode-Solution 鏈接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/ 來源：力扣（LeetCode） 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
浙公網安備 33010602011771號