力扣題目：無重復字符的最長子串

題目解析

方法一：滑動窗口

思路和算法

我們先用一個例子考慮如何在較優的時間復雜度內通過本題。

我們不妨以示例一中的字符串 abcabcbb 為例，找出從每一個字符開始的，不包含重復字符的最長子串，那么其中最長的那個字符串即為答案。對于示例一中的字符串，我們列舉出這些結果，其中括號中表示選中的字符以及最長的字符串：
以 (a)bcabcbb 開始的最長字符串為 (abc)abcbb；
以 a(b)cabcbb 開始的最長字符串為 a(bca)bcbb；
以 ab?abcbb 開始的最長字符串為 ab(cab)cbb；
以 abc(a)bcbb 開始的最長字符串為 abc(abc)bb；
以 abca(b)cbb 開始的最長字符串為 abca(bc)bb；
以 abcab?bb 開始的最長字符串為 abcab(cb)b；
以 abcabc(b)b 開始的最長字符串為 abcabc(b)b；
以 abcabcb(b) 開始的最長字符串為 abcabcb(b)。
發現了什么？如果我們依次遞增地枚舉子串的起始位置，那么子串的結束位置也是遞增的！這里的原因在于，假設我們選擇字符串中的第 k 個字符作為起始位置，并且得到了不包含重復字符的最長子串的結束位置為 r
k
。那么當我們選擇第 k+1 個字符作為起始位置時，首先從 k+1 到 r
k
的字符顯然是不重復的，并且由于少了原本的第 k 個字符，我們可以嘗試繼續增大 r
k
?
，直到右側出現了重復字符為止。
這樣一來，我們就可以使用「滑動窗口」來解決這個問題了
我們使用兩個指針表示字符串中的某個子串（或窗口）的左右邊界，其中左指針代表著上文中「枚舉子串的起始位置」，而右指針即為上文中的 r
k
在每一步的操作中，我們會將左指針向右移動一格，表示 我們開始枚舉下一個字符作為起始位置，然后我們可以不斷地向右移動右指針，但需要保證這兩個指針對應的子串中沒有重復的字符。在移動結束后，這個子串就對應著 以左指針開始的，不包含重復字符的最長子串。我們記錄下這個子串的長度；

在枚舉結束后，我們找到的最長的子串的長度即為答案。

判斷重復字符

在上面的流程中，我們還需要使用一種數據結構來判斷 是否有重復的字符，常用的數據結構為哈希集合（即 C++ 中的 std::unordered_set，Java 中的 HashSet，Python 中的 set, JavaScript 中的 Set）。在左指針向右移動的時候，我們從哈希集合中移除一個字符，在右指針向右移動的時候，我們往哈希集合中添加一個字符。

至此，我們就完美解決了本題。

class Solution {
public:int lengthOfLongestSubstring(string s) {// 哈希集合，記錄每個字符是否出現過unordered_set<char> occ;int n = s.size();// 右指針，初始值為 -1，相當于我們在字符串的左邊界的左側，還沒有開始移動int rk = -1, ans = 0;// 枚舉左指針的位置，初始值隱性地表示為 -1for (int i = 0; i < n; ++i) {if (i != 0) {// 左指針向右移動一格，移除一個字符occ.erase(s[i - 1]);}while (rk + 1 < n && !occ.count(s[rk + 1])) {// 不斷地移動右指針occ.insert(s[rk + 1]);++rk;}// 第 i 到 rk 個字符是一個極長的無重復字符子串ans = max(ans, rk - i + 1);}return ans;}
};

解法二（暴?求解）（不會超時，可以通過）：

 class Solution {public:int lengthOfLongestSubstring(string s) {int ret = 0; 
int n = s.length();
for (int i = 0; i < n; i++){int hash[128] = { 0 };for (int j = i; j < n; j++){hash[s[j]]++; if (hash[s[j]] > 1) break;      ret = max(ret, j - i + 1);}}return ret;}};

附Java代碼

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;}
}