学习顺序主线第 08 / 22 课 · 阶段 3

为什么现在学:把双指针与集合结合,维护连续区间的合法性。

返回算法课程
数组技巧基础

滑动窗口Sliding Window

维护一个连续区间,让左右边界只向前移动,从而避免重复扫描。

45 分钟前置:数组与字符串 · 集合 · 双指针

学完这一课,你应该能做到

  • 明确窗口中的集合为何与区间一致
  • 用 abba 解释多次缩窗
  • 从两个指针的总移动量证明线性时间

01先从一个问题出发

连续听歌时,希望找到一段没有重复歌曲的最长歌单。在字符串中,这就是最长无重复字符子串。

一个具体的例子

text=abba。『保留内容』在缩窗行暂不包含尚未加入的新字符。

哪些暴力工作可以复用

问题是求最长不含重复字符的连续子串长度。连续很关键:可以取 ab,不能跳过两个 b 拼接两边的 a。若为每个起点重新向右检查,很容易反复扫描同一段。

用 left、right 表示当前区间,并用 seen 保存其中字符。向右加入一个新字符之前,旧窗口已经没有重复。此时如果不合法,唯一可能新增的冲突就是新字符与窗口中的同字符重复。于是只需从左边收缩,直到旧的那个同字符被移走。

为什么缩窗要 while,而不是 if

扫描 abba,读到第二个 b 时,旧窗口是 ab。先移走最左边 a,剩下 b,重复并没有消失;还要移走旧 b,才能加入新 b。如果只删一次就停,集合和窗口内容就无法正确表达『没有重复』。

收缩到刚刚合法时,left 是当前 right 下仍能维持合法的最早边界,所以当前窗口是以 right 结尾的最长合法子串。每个 right 都检查一次并更新 best,就覆盖了全局最长子串可能的结尾。

02最直接的办法,为什么慢?

固定每个起点,向右扩展并用集合检查重复。

暴力 · O(n²)

相邻起点重复检查大量相同字符。在字符互不相同的最坏情形下,扫描次数是 n+(n−1)+…+1。

03一步步,推导出优化思路

1

发现重复工作

检查 abc 后,把起点移动到 b 时,又要重新扫描 bc。已有的信息本可以保留。

2

保存窗口中的信息

使用集合保存当前窗口内的字符。右端新字符到来时,可以平均 O(1) 判断是否重复。

3

只移走导致失效的部分

若新字符已在集合中,反复移走左端字符,直到不再重复,再加入新字符并更新答案。

贯穿算法的不变量

每次更新 best 时,窗口 [left, right] 中没有重复字符,集合恰好保存这个窗口的字符。

拿一个小输入,逐步手算

text=abba。『保留内容』在缩窗行暂不包含尚未加入的新字符。

right / 新字符操作left / 保留内容best
0 / a直接加入 a0 / a1
1 / b直接加入 b0 / ab2
2 / b重复,先移走 a1 / b(新 b 未入)2
2 / b仍重复,再移走旧 b2 / 空2
2 / b加入新 b2 / b2
3 / a加入 a2 / ba2

最长长度为 2,ab 和 ba 都是合法答案。best 记录全程最大值,不是最后一个窗口的长度。

合法性与不漏最优解是两个步骤

  1. 初始空窗口无重复。每次扩展前,seen 与旧窗口字符完全一致。
  2. 只在新字符已存在时缩窗,直到它不再存在;再加入新字符,恢复无重复窗口和集合的一致性。
  3. 被移除的更早起点含有与新字符冲突的旧副本,不可能形成以当前 right 结尾的合法更长子串。逐个结尾更新最大值,得到全局答案。

04让每一步,都看得见

试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。

Sliding Window交互演示
STEP 01 / 16
a
0left
b
1
b
2
a
3

橙色:当前字符 · 绿色:当前窗口 · 淡色:窗口外

当前处理已处理 / 已确定未处理
01

维护一个没有重复字符的连续窗口。

sliding_window.py参考实现 · 当前第 2 行
正在载入代码编辑器…

动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。

代码里的每个关键决定

while char in seen:
每次删除后重新检查。使用 if 会在 abba 这类输入上保留冲突,而不是仅仅慢一点。
seen.remove(text[left])
删除左端实际离开的字符,再增加 left。不要只移动下标却不更新集合,否则后面的成员查询会读取过期状态。
seen.add(char)
冲突消除后才加入新字符。如果使用计数字典而非集合,也要维持与窗口内容对应的计数。
best = max(best, right - left + 1)
加入新字符后窗口是闭区间 [left,right],长度需要 +1。此时才可以用其合法长度更新答案。

05复杂度,来自具体的工作量

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

虽然 while 写在 for 内,但 right 走 n 次,left 最多也走 n 次。每个字符最多入集合、出集合各一次;假设哈希操作平均 O(1),总时间 O(n)。

辅助空间
O(min⁡(n,∣Σ∣))O(\min(n, |\Sigma|))

集合最多保存窗口内互不相同的字符,数量不超过字符串长度 n 和字符集大小 |Σ| 的较小值。JavaScript 示例另外把字符串展开为码点数组,占 O(n)。

拖动 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这些细节,容易踩坑

01

收缩用 while,不一定只移一次

abba 在最后一个 b 到来时,要先移 a 再移 b,才能恢复无重复。

02

先恢复合法,再记录答案

包含重复字符的临时窗口不能用于更新最长长度。

03

不是所有连续问题都适用

含负数的子数组和不具备简单单调收缩条件,常要使用前缀和 + 哈希表。

用反例检查前提

有两个指针不代表任何区间题都能滑窗

另一类『和至少为目标』问题常在和够大时缩窗。若数组含负数,缩窗可能使和增大、扩窗可能使和减小,基于单调性的排除规则就可能失效。

怎样修正:先说明维护的合法条件,以及移动边界为什么安全。本题维护的是字符唯一性,这个条件允许上述收缩;区间和问题需要重新证明,必要时用前缀和等结构。

08把想法带进真实题目

合上答案,自己推一次

把 best 与当前长度分开

手算 abcabcbb,写出每个 right 处理完成后的 left 和窗口长度。最终窗口很短,为什么答案仍是 3?

需要一点提示

right=3 的 a 会让 left 移到 1;之后一直维护无重复。

查看完整推导与答案
  1. left 依次为 0、0、0、1、2、3、5、7。
  2. 对应窗口长度为 1、2、3、3、3、3、2、1。
  3. best 保存这些长度的最大值 3;只返回最后窗口长度会错误返回 1。

完成上面的手算练习,再把思路迁移到这些题目。

09不用背模板,回答这几个问题

01嵌套 while 为什么没有导致 O(n²)?

02窗口为 ab,读到第二个 b 后该怎么做?

03含负数数组的精确子数组和,首先考虑?

你已经走完了这次推导。

能用自己的话解释复杂度和不变量,再标记为掌握。

把知识连起来

继续阅读

本课例子与推导为本站编写。需要另一种表述或进一步学习时,可对照这些公开课程与文档:

MIT 6.006 · 算法讲义Princeton Algorithms · 课程资料

能独立完成本课练习,再标记掌握。也可以直接用上面的链接继续学习。