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

题意

给定一个字符串，求不含重复字符的最长连续子串长度。

思路

标准滑动窗口：

1. 右指针不断向右扩张，把新字符加入窗口。
2. 如果出现重复字符，就移动左指针并清理计数。
3. 每次维护窗口长度最大值。

这个题真正值得记住的不是代码，而是窗口的状态维护方式：

• 窗口里保存的是“当前合法区间”
• 重复条件出现时，只修复到重新合法为止
• 最大值更新通常放在窗口合法后

代码

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> cnt;
    int ans = 0;
    for (int left = 0, right = 0; right < (int)s.size(); right++) {
        cnt[s[right]]++;
        while (cnt[s[right]] > 1) {
            cnt[s[left]]--;
            left++;
        }
        ans = max(ans, right - left + 1);
    }
    return ans;
}

易错点

• 不要在发现重复后只移动一次左指针，应该循环缩小窗口。
• 更新答案时机要在窗口恢复合法之后。

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(字符集大小)

复盘

刷滑动窗口时，可以把题目先分类成：

• 固定窗口
• 最长合法区间
• 最短满足区间

这样在看到新题时更容易快速套框架。