双指针

01 / 共享的机制

两个下标在同一序列上移动以维持某个 不变式 — 移动规则在子模式间各不相同, 但底层机制是相通的。

02 / 一句话本质
当你需要一段满足条件的连续区间时, 从右侧扩张直到条件破坏,然后 从左侧收缩直到条件再次成立。
题目和 ≤ k 的最长子数组输入[3, 1, 2, 1, 4, 2, 1, 5]k8
30
11
22
13
44
25
16
57
准备就绪。按 play 从右侧开始扩张窗口。
步
0 / 27
窗口和
0
当前长度
0
目前最优
0
0 / 27

03 / 模式骨架

# 一条序列上的两个下标left, right ← 0while right < n:// 1. 扩张窗口将 arr[right] 纳入状态while 不变式被破坏:移除 arr[left]; left++// 2. 记录当前合法窗口best ← max(best, right − left + 1)right++

04 / 什么时候用这个模式

"连续区间"
答案是数组的一段切片,而不是子集。 如果可以重排,这就不是合适的工具。
"最长 / 最短"
你在约束下优化这段连续切片的长度。
"至多 k"
一个单调约束:若 [l,r] 满足,则其内部更小的窗口也一定满足。 这就是窗口所依赖的不变式。
"k 种不同"
内部状态变成多重集,但机制完全相同。

05 / 常见坑

i.
收缩用 while,而不是 if。
单次收缩往往无法恢复不变式。内层循环必须运行到窗口重新合法 — 否则你会把一个破碎的窗口带到下一步。
ii.
在错误的时刻记录答案。
应当在收缩之后窗口合法时再更新 best,而不是在收缩过程中。 中间的脏状态不是答案。
iii.
窗口长度的边界差一。
闭区间下长度为 right − left + 1;半开区间下为 right − left。选定一种约定后,绝不混用。

06 / 去 LeetCode 上练习

四道题,按难度排序。这里有意不放解答。

01Maximum Average Subarray I— LC 643简单→02Longest Substring Without Repeating Characters— LC 3中等→03Longest Substring with At Most K Distinct Characters— LC 340中等→04Minimum Window Substring— LC 76困难→

— / 什么时候用哪个

对向
当数组已排序且答案是一对时使用。
两数之和 · 回文 · 容器
快 / 慢
用于原地修改或环的检测。
去重 · 链表环
滑动窗口
当条件围绕一段连续区间时使用。
最长/最短 · 至多 k