通过unordered_set来判断字符是否出现过,通过两个指针维护无重复字符子串,如果字符没有出现过,则将字符插入unorder_set,否则不断的移除左指针指向的元素,直到右指针指向的元素不在unordered_set中。AC代码如下:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> hash_set;
        int i = 0,j = 0,maxlen = 0,n = s.size();
        while(i<n && j<n){
            if(hash_set.count(s[j]) == 0){
                hash_set.insert(s[j++]);
                maxlen = max(maxlen,j - i);
            }else{
                hash_set.erase(s[i++]);
            }
        }
        return maxlen;
    }
};

使用滑动窗口套路解决该问题:

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

运行效率:

Runtime: 16 ms, faster than 70.89% of C++ online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 8.4 MB, less than 68.38% of C++ online submissions for Longest Substring Without Repeating Characters.

2021.06.20 更新
一种更好理解的滑动窗口解法

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size(),rk = -1,ans = 0;
        unordered_set<int> visit;

        for(int i = 0;i < n;i++)
        {
            if(i != 0) visit.erase(s[i-1]);
            while(rk + 1 < n && !visit.count(s[rk + 1]))
            {
                visit.insert(s[rk + 1]);
                rk++;
            }
            ans = max(ans,rk - i + 1);
        }
        return ans;
    }
};