無重復字符的最長子串原題地址
方法一：滑動窗口（雙指針） + 哈希集合
考慮找出字符串s的所有的無重復字符的子串，求出這些子串長度的最大值即可。
使用下標 [left,right] 來維護子串。我們只需要找到每一個 left 對應的所有 right 即可，換句話說，固定了 left 之后，我們讓 right 從 left?的位置開始，向后滑動，直到 [left,right] 出現重復字符為止。
以下為所有無重復字符的子串：
(a) b c a b c b b
(a b) c a b c b b
(a b c) a b c b b
a (b) c a b c b b
a (b c) a b c b b
a (b c a) b c b b
a b (c) a b c b b
a b (c a) b c b b
a b (c a b) c b b
a b c (a) b c b b
a b c (a b) c b b
a b c (a b c) b b
a b c a (b) c b b
a b c a (b c) b b
a b c a b (c) b b
a b c a b (c b) b
a b c a b c (b) b
a b c a b c b (b)由于我們要找的是這些子串中最長的那個，所以固定 left 后，先讓 right 右移至出現重復字符或者 right 移動到字符串的末尾，再統計該子串的長度，即 right-left+1 ，求出其中的最大值即可。
需要統計如下子串的長度：
(a b c) a b c b b
a (b c a) b c b b
a b (c a b) c b b
a b c (a b c) b b
a b c a (b c) b b
a b c a b (c b) b
a b c a b c (b) b
a b c a b c b (b)顯然，當某條子串 [left,right] 的右端點 right 已經到達字符串的末尾時，若 left 繼續右移，只會縮短子串長度，所以此時無需繼續統計。
為了判斷子串是否已經出現重復字符，可以利用哈希集合（如?C++ 中的 unordered_set<char> ），來存儲 [left,right] 中的所有字符，當 right 右移時，就把最右邊的字符添加到哈希集合中；當 left 右移時，就把最左邊的字符從哈希集合中刪除。這樣，每次只需判斷子串新增加的字符是否已經在哈希集合中出現過即可。
// 方法一：滑動窗口
class Solution
{
public:int lengthOfLongestSubstring(string s){if (s.empty()){return 0;}unordered_set<char> us;int ans = 0;// [left,right] 表示子串int left = 0, right = 0;us.insert(s[0]);while (1){// 右指針右移，直到出現重復字符while (right + 1 < s.size() && !us.count(s[right + 1])){us.insert(s[++right]);}// 子串長度為 right-left+1ans = max(ans, right - left + 1);// 右指針走到尾，子串不可能更長if (right == s.size() - 1){break;}// 左指針右移，在哈希表中去掉最左邊的字符us.erase(s[left++]);}return ans;}
};方法二：對方法一的優化，實現左指針 left 的快速跳轉
方法一是固定 left ，讓 right 盡可能右移，從而統計所有的 [left,right] 區間長度 right-left+1 的最大值，這樣最壞情況下 left 會遍歷完整個字符串。
考慮用 key-value 模型的哈希表（如?C++ 中的 unordered_set<char, int> ），每次把 [0,right] 的字符及其對應下標都存進去。
我們用 right 遍歷字符串，若 right 右移后指向的字符在哈希表中出現過，且最后出現的下標在 [left,right] 的范圍內，說明此時的子串 [left,right] 已經出現了重復字符，此時 left 應該跳轉到 s[right] 最后一次出現的位置的后面。
下面的例子中， right 本來指向 f ，右移后指向 c ， left 就要從 a 直接跳轉到第一個 c 后面，否則 [left,right] 會出現重復字符。
(a b c d e f) c
a b c (d e f c)每次 right 右移后，都要把 s[right] 及對應的下標 right 都存儲到哈希表中，也就是把 s[right] 當前最后出現的位置存儲到哈希表中。
// 方法二：滑動窗口優化
class Solution
{
public:int lengthOfLongestSubstring(string s){if (s.size() <= 1){return s.size();}unordered_map<char, int> um;int ans = 0;// [left,right] 表示子串int left = 0, right = 0;um[s[0]] = 0;// 右指針右移，直到出現重復字符while (++right < s.size()){auto it = um.find(s[right]);// 出現重復字符if (it != um.end()){// 左指針跳轉到重復字符上一次出現的位置之后left = max(left, it->second + 1);}// 子串長度為 right-left+1ans = max(ans, right - left + 1);um[s[right]] = right;}return ans;}
};
)
