跳转至

3 无重复字符的最长子串

和其他滑动窗口子串问题不同: - 本题没有使用两个子串s和t - 比较的子串没有重复字符,这意味着不需要使用valid和need

为什么使用滑动窗口 -> 因为题目问的是子串,即连续字符序列

判断字符是否重复 -> 用哈希表维护滑动窗口的字符

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> window;
        int left = 0, right = 0;
        int len = 0;
        while(right < s.size()){
            char c = s[right];
            right++;
            window[c]++;
            while(window[c] > 1){           
                char d = s[left];
                left++;
                window[d]--;
            }
            // 更新结果在收缩外,因为收缩表示还有重复字符
            // 结果统计的是没有重复字符的情况
            len = max(len, right - left);
        }
        return len;
    }
};
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        int start = 0;
        unordered_set<char> hashMap;
        int ans = 0;
        for(int end = 0; end < n; end++){
            while(hashMap.count(s[end])){
                // 这里注意是把s[start]移除
                hashMap.erase(s[start]);
                start++;
            }
            hashMap.insert(s[end]);
            ans = max(ans,end - start + 1);
        }
        return ans;
    }
};

时间复杂度:\(O(n)\)

空间复杂度:\(O(n)\)