Problem: *************

思路

解决此题的方法是需要用到哈希表作为辅助记录，之所以选择哈希表作为辅助记录容器主要是因为查找时间复杂度为$O(1)O(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]

当右边界遇到出现过的字符时，左边界滑动到相同的字符位置的下一个位置，然后在哈希表中将相应的字符删除掉，保证子串字符不重复，至到循环结束。

复杂度

• 时间复杂度:

遍历字符串一次，因此时间复杂度为$O(n)O(n)$

• 空间复杂度:

使用到了哈希表，因此空间复杂度为$O(n)O(n)$

Code

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n=s.size();
        if(n==0) return 0;
        int left=0,right=0,ans=0;
        unordered_map<char,int> m;
        while(right<n)
        {
            ++m[s[right]];
            while(m[s[right]]>1)
            {
                --m[s[left++]];
            }
            ans=max(ans,right-left+1);
            ++right;
        }
        return ans;
    }
};

在本题的基础上还可以进行拓展，我们将输出改为输出最长子串本身而不是长度：

Code

​
class Solution {
public:
    string lengthOfLongestSubstring(string s) {
        int n=s.size();
        if(n==0) return 0;
        int left=0,right=0,ans=0;
        string str;
        unordered_map<char,int> m;
        while(right<n)
        {
            ++m[s[right]];
            while(m[s[right]]>1)
            {
                --m[s[left++]];
            }
            str=right-left+1>ans?s.substr(left,right):str;//必须在ans更新的前面
            ans=max(ans,right-left+1);
            ++right;
        }
        return str;
    }
};