3. 无重复字符的最长子串

题目链接

解题思路

• 子串问题，思考，「以i开头」结果是什么，求出所有的结果，然后最长的那个就是答案。或者「以i结尾」结果是什么，求出所有的结果，最长的那个就是答案。
• 本题使用「以i开头」结果是什么。
• 当求出i开头的结果是[i, j]，那么怎么求i+1的结果？其实就是滑动窗口。现在的窗口是[i, j]，然后把i移除窗口，看窗口右侧是否还能进来。

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        if (n == 0) {
            return 0;
        }
        unordered_set<char> has;
        int ans = 1;
        int l = 0;
        int r = 1;
        has.insert(s[0]);
        while(r < n) {    // r能够进来吗？
            if (has.count(s[r]) == 0) {
                has.insert(s[r]);
                r++;
            } else {
                has.erase(s[l]);
                l++;
            }
            ans = max(ans, r - l);
        }
        return ans;
    }
};