01先从一个问题出发
连续听歌时,希望找到一段没有重复歌曲的最长歌单。在字符串中,这就是最长无重复字符子串。
text=abba。『保留内容』在缩窗行暂不包含尚未加入的新字符。
哪些暴力工作可以复用
问题是求最长不含重复字符的连续子串长度。连续很关键:可以取 ab,不能跳过两个 b 拼接两边的 a。若为每个起点重新向右检查,很容易反复扫描同一段。
用 left、right 表示当前区间,并用 seen 保存其中字符。向右加入一个新字符之前,旧窗口已经没有重复。此时如果不合法,唯一可能新增的冲突就是新字符与窗口中的同字符重复。于是只需从左边收缩,直到旧的那个同字符被移走。
为什么缩窗要 while,而不是 if
扫描 abba,读到第二个 b 时,旧窗口是 ab。先移走最左边 a,剩下 b,重复并没有消失;还要移走旧 b,才能加入新 b。如果只删一次就停,集合和窗口内容就无法正确表达『没有重复』。
收缩到刚刚合法时,left 是当前 right 下仍能维持合法的最早边界,所以当前窗口是以 right 结尾的最长合法子串。每个 right 都检查一次并更新 best,就覆盖了全局最长子串可能的结尾。
02最直接的办法,为什么慢?
固定每个起点,向右扩展并用集合检查重复。
相邻起点重复检查大量相同字符。在字符互不相同的最坏情形下,扫描次数是 n+(n−1)+…+1。
03一步步,推导出优化思路
发现重复工作
检查 abc 后,把起点移动到 b 时,又要重新扫描 bc。已有的信息本可以保留。
保存窗口中的信息
使用集合保存当前窗口内的字符。右端新字符到来时,可以平均 O(1) 判断是否重复。
只移走导致失效的部分
若新字符已在集合中,反复移走左端字符,直到不再重复,再加入新字符并更新答案。
每次更新 best 时,窗口 [left, right] 中没有重复字符,集合恰好保存这个窗口的字符。
拿一个小输入,逐步手算
text=abba。『保留内容』在缩窗行暂不包含尚未加入的新字符。
| right / 新字符 | 操作 | left / 保留内容 | best |
|---|---|---|---|
| 0 / a | 直接加入 a | 0 / a | 1 |
| 1 / b | 直接加入 b | 0 / ab | 2 |
| 2 / b | 重复,先移走 a | 1 / b(新 b 未入) | 2 |
| 2 / b | 仍重复,再移走旧 b | 2 / 空 | 2 |
| 2 / b | 加入新 b | 2 / b | 2 |
| 3 / a | 加入 a | 2 / ba | 2 |
最长长度为 2,ab 和 ba 都是合法答案。best 记录全程最大值,不是最后一个窗口的长度。
合法性与不漏最优解是两个步骤
- 初始空窗口无重复。每次扩展前,seen 与旧窗口字符完全一致。
- 只在新字符已存在时缩窗,直到它不再存在;再加入新字符,恢复无重复窗口和集合的一致性。
- 被移除的更早起点含有与新字符冲突的旧副本,不可能形成以当前 right 结尾的合法更长子串。逐个结尾更新最大值,得到全局答案。
04让每一步,都看得见
试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。
橙色:当前字符 · 绿色:当前窗口 · 淡色:窗口外
维护一个没有重复字符的连续窗口。
动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。
代码里的每个关键决定
while char in seen:- 每次删除后重新检查。使用 if 会在 abba 这类输入上保留冲突,而不是仅仅慢一点。
seen.remove(text[left])- 删除左端实际离开的字符,再增加 left。不要只移动下标却不更新集合,否则后面的成员查询会读取过期状态。
seen.add(char)- 冲突消除后才加入新字符。如果使用计数字典而非集合,也要维持与窗口内容对应的计数。
best = max(best, right - left + 1)- 加入新字符后窗口是闭区间 [left,right],长度需要 +1。此时才可以用其合法长度更新答案。
05复杂度,来自具体的工作量
虽然 while 写在 for 内,但 right 走 n 次,left 最多也走 n 次。每个字符最多入集合、出集合各一次;假设哈希操作平均 O(1),总时间 O(n)。
集合最多保存窗口内互不相同的字符,数量不超过字符串长度 n 和字符集大小 |Σ| 的较小值。JavaScript 示例另外把字符串展开为码点数组,占 O(n)。
把工作量具体数出来
right 从左到右经过 n 个字符一次,left 也最多增加 n 次。即使写成 for 内嵌 while,总移动量也不超过 2n,时间期望 O(n)。
seen 存当前窗口中的不同字符,最多 min(n,字符种类数) 个。JavaScript 为按 Unicode 码点遍历创建 Array.from(text),这份数组另外占 O(n)。
Python 与 JavaScript 示例按码点处理;本页 C++ string 示例注明 ASCII 限制。用户眼中的一个字形可能由多个码点组成,不能把这些计数单位混为一谈。
06看到什么,应该想到它?
这些特征值得停下来想一想:
07这些细节,容易踩坑
收缩用 while,不一定只移一次
abba 在最后一个 b 到来时,要先移 a 再移 b,才能恢复无重复。
先恢复合法,再记录答案
包含重复字符的临时窗口不能用于更新最长长度。
不是所有连续问题都适用
含负数的子数组和不具备简单单调收缩条件,常要使用前缀和 + 哈希表。
有两个指针不代表任何区间题都能滑窗
另一类『和至少为目标』问题常在和够大时缩窗。若数组含负数,缩窗可能使和增大、扩窗可能使和减小,基于单调性的排除规则就可能失效。
怎样修正:先说明维护的合法条件,以及移动边界为什么安全。本题维护的是字符唯一性,这个条件允许上述收缩;区间和问题需要重新证明,必要时用前缀和等结构。
08把想法带进真实题目
把 best 与当前长度分开
手算 abcabcbb,写出每个 right 处理完成后的 left 和窗口长度。最终窗口很短,为什么答案仍是 3?
需要一点提示
right=3 的 a 会让 left 移到 1;之后一直维护无重复。
查看完整推导与答案
- left 依次为 0、0、0、1、2、3、5、7。
- 对应窗口长度为 1、2、3、3、3、3、2、1。
- best 保存这些长度的最大值 3;只返回最后窗口长度会错误返回 1。
完成上面的手算练习,再把思路迁移到这些题目。
09不用背模板,回答这几个问题
01嵌套 while 为什么没有导致 O(n²)?
02窗口为 ab,读到第二个 b 后该怎么做?
03含负数数组的精确子数组和,首先考虑?
你已经走完了这次推导。
能用自己的话解释复杂度和不变量,再标记为掌握。