3. 无重复字符的最长子串 (Medium)
专题归类： 02-双指针与滑动窗口 · 01-哈希表 LeetCode 链接： https://leetcode.cn/problems/longest-substring-without-repeating-characters/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。
示例：
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3
补充说明：
- 字符串长度范围：
0 <= s.length <= 5 * 10^4 - 字符串由英文字母、数字、符号和空格组成（ASCII 字符集）
题目详细分析
数据范围含义：
- 长度最大 5×10^4，O(n^2) 会超时（2.5×10^9 次操作），需要 O(n) 解法。
- 字符集为 ASCII（128 个字符），而不是仅限小写字母。这对哈希表的大小有影响——不能用固定 26 的数组，但可以用 128 的数组，或者直接用哈希集合/字典。
核心概念：
- 子串（substring） 是原字符串中连续的一段，不是子序列（subsequence）。
- 不含有重复字符意味着子串中每个字符最多出现一次。
- 目标是最大长度，不是子串本身。
边界条件：
- 空字符串：长度为 0，结果为 0。
- 字符串全为同一字符：如 “aaaaa”，最长无重复子串长度为 1。
- 字符串全无重复：如 “abcde”，最长无重复子串就是整个字符串，长度 len(s)。
- 单个字符：长度为 1，结果为 1。
隐藏条件：
- 滑动窗口是解决子串问题的标准模板。核心是维护一个”窗口”，用哈希表记录窗口内的字符出现情况。
- 窗口的”扩大”和”缩小”对应着 right 和 left 指针的移动。
- 可以用哈希集合存储窗口内字符，也可以用哈希字典存储每个字符最后出现的位置（实现”跳跃式”移动 left）。
小白版直白理解
想象你在看一条长长的彩带，上面画着各种符号。你想找到最长的一段，这段里面没有重复的符号。
笨办法： 从每个位置开始，往右看，记下看到过的符号，直到遇到重复的为止。每个起点都试一遍。
聪明办法（滑动窗口）： 你拿一个放大镜（窗口）在彩带上从左往右滑：
- 放大镜的右端不断往右移动，看到新符号就收进来。
- 如果新符号和放大镜里已有的符号重复了，就把放大镜的左端往右缩，直到把重复的符号”挤出去”。
- 每次右端移动后，记下放大镜当前覆盖的长度，取最大值。
这个过程就像一条毛毛虫在彩带上爬行——头往前伸，如果遇到障碍就把尾巴往前收。整个过程只需要爬一次！
解题思路
思路一：滑动窗口 + 哈希集合（推荐，容易理解）
核心想法： 用哈希集合 char_set 存储当前窗口内的字符。右指针扩展窗口，如果遇到重复字符，左指针收缩直到窗口内无重复。
三问法分析：
- 什么时候扩大？ 右指针字符加入后无重复 → 右移 right。
- 什么时候缩小？ 出现重复字符 → 左移 left 直到无重复。
- 什么时候更新答案？ 扩大窗口后（窗口变大，可能产生更优解）。
def lengthOfLongestSubstring(s):
"""
滑动窗口 + 哈希集合
char_set 记录窗口内的字符，用于检测重复
"""
char_set = set()
left = 0
max_len = 0
for right, ch in enumerate(s):
# 如果 ch 重复，收缩左边界直到窗口内无重复
while ch in char_set:
char_set.remove(s[left])
left += 1
# 加入当前字符
char_set.add(ch)
# 更新最大长度
max_len = max(max_len, right - left + 1)
return max_len思路二：滑动窗口 + 哈希字典（优化版，跳跃式移动 left）
核心想法： 不用逐个移动 left，而是用字典记录每个字符最近一次出现的位置。遇到重复字符时，直接将 left 跳到 上次出现位置 + 1。
关键洞察： 思路一中，while 循环逐个移除字符是 O(1) 摊销，但可以有更直接的方式——如果知道重复字符的位置，可以直接跳过去。
def lengthOfLongestSubstring(s):
"""
滑动窗口 + 哈希字典（优化版）
char_index 记录每个字符最近一次出现的位置
left 可以直接跳跃到重复字符的下一个位置
"""
char_index = {} # 字符 -> 最近一次出现的下标
left = 0
max_len = 0
for right, ch in enumerate(s):
# 如果 ch 出现过且在窗口内，直接跳跃 left
if ch in char_index and char_index[ch] >= left:
left = char_index[ch] + 1
# 记录当前字符的位置
char_index[ch] = right
# 更新最大长度
max_len = max(max_len, right - left + 1)
return max_len两个版本对比：
| 版本 | left 移动方式 | 空间 | 特点 |
|---|---|---|---|
| 集合版 | 逐个移动 | O(k) | 直观，适合初学者 |
| 字典版 | 跳跃移动 | O(k) | 更高效，但需要处理”过期”字符 |
易错点
- 子串 vs 子序列： 子串必须连续，不重复子序列可以跳过中间字符。题目要求的是子串，所以用滑动窗口。如果搞成子序列，就变成完全不同的题了。
- 字典版中 left 不能回退： 需要检查
char_index[ch] >= left，因为char_index中可能记录了该字符但不在当前窗口中（已经被 left 越过了）。如果不加这个判断，left 可能错误地”回退”到更早的位置。 - 字符集大小： 题目中字符集是 ASCII，不是仅限小写字母。如果用固定数组，需要 128 或 256 大小，不能只开 26。
- 空字符串处理： s 可能为空，此时 max_len 保持为 0，直接返回 0。
- 更新答案的时机： 是在窗口扩大后（right 移动后）更新，不是在窗口收缩时。对集合版来说，while 移除重复后立即更新。对字典版来说，跳跃 left 后立即更新。
框架提炼
滑动窗口通用模板：
滑动窗口是解决”连续子串/子数组”问题的标准框架，核心是用两个指针维护一个窗口，避免重复遍历。
def sliding_window(s):
"""
滑动窗口通用模板
"""
window = {} # 或 set/list，记录窗口内元素
left = 0
result = 0 # 或初始化为极小值/极大值
for right, val in enumerate(s):
# 1. 扩展窗口：加入右指针元素
add_to_window(window, val)
# 2. 收缩窗口：当窗口不满足约束时，移动左指针
while not is_valid(window):
remove_from_window(window, s[left])
left += 1
# 3. 更新答案：窗口满足约束时
result = max(result, right - left + 1) # 或 min
return result滑动窗口三问法：
- 什么时候扩大窗口？（右移 right）
- 什么时候缩小窗口？（左移 left）
- 什么时候更新答案？（扩大后 / 缩小前）
关联题目
- 76-最小覆盖子串 — 同样是滑动窗口，但本题是”找最长无重复”（约束是不重复），76 是”找最短覆盖”（约束是全覆盖）。本题窗口收缩条件是有重复，76 是已经全覆盖
- 438-找到字符串中所有字母异位词 — 定长滑动窗口，窗口大小固定为 len(p)，每次滑动后比较窗口内字符计数与目标是否一致。本题是不定长窗口
- 159-至多包含两个不同字符的最长子串 — 本题的变体，约束条件从”无重复”变为”最多两种不同字符”，滑动窗口模板思路完全一致，只需修改收缩条件