无重复字符的最长子串

🟡 Medium · 🏷️ 字符串、哈希表、滑动窗口 · LeetCode#3

📖 题目

给定字符串 s，找出不含重复字符的最长子串的长度。

输入："abcabcbb"
输出：3（"abc"）

输入："pwwkew"
输出：3（"wke"）

💡 思路

滑动窗口 + 集合判重：右指针不断扩展窗口，一旦遇到重复字符就收缩左边界直到窗口内不再重复，每次扩大后记录一次最长长度。for right 可以理解为"以右端点作为结束来枚举"。

判重必须先判断再收缩，收缩完再加入——集合的 add 会直接吞掉重复元素，如果先加再判断就检测不到重复了：

c = {'a'}
c.add('a')   # c 还是 {'a'}，看不出重复

💻 代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        c = set()
        max_len = 0
        left = 0
        for right in range(len(s)):
            while s[right] in c:      # 有重复，收缩
                c.remove(s[left])
                left += 1
            c.add(s[right])           # 无重复，加入
            max_len = max(max_len, right - left + 1)
        return max_len

时间复杂度 O(n)，空间复杂度 O(min(n, m))，m 为字符集大小。

🔀 跟 209 对比

同样是滑动窗口，209 找最短、这题找最长，收缩的时机正好相反：

	209 最短子数组	3 最长子串
状态	数字求和	字符判重
收缩条件	sum >= target	s[right] in set
操作顺序	先加，后收缩	先收缩，后加
记录时机	收缩时（找最短）	扩大后（找最长）