1. 題意

2. 分析：

   • 我們可以將所給的長度為n的字符串，對串中的每一個字符，求得以該字符為結(jié)尾的最長無重復(fù)字符的子串。所有字串長度的最大值，便是要尋找的答案。
   • 如果以s[i]為結(jié)尾的最長無重復(fù)字符的子串起始位置為j，那么當(dāng)s[i]遍歷到下一個位置s[i + 1]時，此時最長無重復(fù)字符的子串起始位置J一定在j的右邊或者保持j位置不變，一定不會出現(xiàn)在j的左邊?？梢酝ㄟ^反證法來證明，倘若當(dāng)s[i]遍歷到下一個位置s[i + 1]時，最長無重復(fù)字符的子串起始位置J在j的左邊，那么在s[i]還沒有遍歷到s[i + 1]這個字符的時候，最長無重復(fù)字符子串的起始位置一定也在j的左邊而非j，這就否定了我們原來的假設(shè)，得出矛盾，因此命題得證，即：
     <font color="#660000">如果以s[i]為結(jié)尾的最長無重復(fù)字符的子串起始位置為j，那么當(dāng)s[i]遍歷到下一個位置s[i + 1]時，此時最長無重復(fù)字符的子串起始位置J一定在j的右邊或者保持j位置不變</font><br />
   • 因此，這樣就將我們算法的時間復(fù)雜度降低了一維，在進(jìn)行j位置的搜索時，直接從上一狀態(tài)向右搜索即可。

3. 代碼：
   C++代碼：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> hash; // 建立哈希表（使用unordered_map<char,int> int字段默認(rèn)初始化為0）
        int res = 0; // 定義答案
        for (int i = 0, j = 0; i < s.size(); i++){
            hash[s[i]] ++;  // 把s[i + 1]加入哈希表，此時，如果出現(xiàn)了重復(fù)字符，那么hash[s[i]]的值會變成2。
            while(hash[s[i]] > 1)   hash[s[j++]]--;
            /*
            hash[s[j++]]--;
            這句話的意義在于，當(dāng)我們發(fā)現(xiàn)了重復(fù)字符s[i]之后，那么從j位置起，將hash[s[j]]的值減1，并且將j的值增加1，直到我們找到了重復(fù)的字符串，結(jié)束循環(huán)。
            拿字符串“zuabca”來說，當(dāng)遍歷到第二個‘a(chǎn)’時，此時i=3，j=0，
            （1）將hash[s[j]]的值減1，目的是為了刪除重復(fù)的字符；
            （2）將j的值加1（右移），目的是為了計算最長無重復(fù)字符子串的長度；
            我們會發(fā)現(xiàn)，這樣進(jìn)行的話，會將hash['z'], hash['u']的值也給減1了，我們本想將重復(fù)字符‘a(chǎn)’的hash值變成1，即hash['a'] == 1,但是此時出現(xiàn)了這樣的結(jié)果：hash['z'] == hash['u'] == 0，hash['a'] == 1。
            這樣的話，對我們解題來說，無所謂！因為前面推導(dǎo)出j是單調(diào)向右的，不會再向左了，第一個‘a(chǎn)’的左邊的hash['z'], hash['u']變成什么樣子,我們都不再去用它了。
            */
            res = max(res, i - j + 1);  // 找到所有子串的最大值，即為最終結(jié)果。
        }
        return res;
    }
};

Python代碼：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        Hash = dict()
        j, res = 0, 0
        for i in range(len(s)):
            Hash[s[i]] = Hash[s[i]] + 1 if s[i] in Hash else 1
            while Hash[s[i]] > 1:
                Hash[s[j]] -= 1
                j += 1
            res = max(res, i - j + 1)
        return res

4. 總結(jié)：
   • 本題主要用到了雙指針?biāo)惴?哈希表知識點，通過分析發(fā)現(xiàn)首指針j不會向左移動，因此時間復(fù)雜度降為。