双指针

01 / 共享的机制

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

02 / 一句话本质
两个指针以不同速度遍历同一序列 — 速度差让你能原地压缩、定位中点, 或在不借助额外内存的情况下检测环。
题目在有序数组上就地去除重复元素输入[1, 1, 2, 2, 3, 3]
10
11
22
23
34
35
输入有序。首元素总是保留 — slow 置于 0,fast 从 1 开始扫描。
步
0 / 8
slow · fast
0 · —
动作
初始化
目前唯一值数
1
0 / 8

03 / 模式骨架

# 原地压缩变体slow ← 0for fast in 1..n−1:if arr[fast] ≠ arr[slow]:slow++arr[slow] ← arr[fast]return slow + 1# 检测环变体:fast 步长为 2,slow 步长为 1 — 当且仅当存在环时它们相遇

04 / 什么时候用这个模式

"原地"
必须就地修改输入,不能开辟第二个数组。 slow 标记下一个被保留元素应当放置的位置。
"环"
在链表或指针链中检测或定位环。 fast 的速度是 slow 的两倍 — 当且仅当存在环时它们相遇。
"中点"
一次遍历找到链表中点:当 fast 到达末尾时,slow 正好在中间。
"压缩 / 划分"
将满足某个谓词的元素保留在前段,其余丢弃。与去重机制相同,只是保留条件不同。

05 / 常见坑

i.
将两个指针初始化到同一位置。
压缩问题中,slow 从 0 开始,fast 从 1 开始; 环检测中两者都从头节点开始 — 但 fast 在首次比较之前先前进。每个问题选定相应的约定。
ii.
在错误的时机推进 slow。
写入之前更新 slow,而不是之后 — 否则会覆盖上一个保留的值。 这里的差一,正是结果正确与整体平移之间的差距。
iii.
与滑动窗口混淆。
滑动窗口刻画的是一段连续区间的大小;快慢指针利用速度差 — 两指针之间的间隔本身就是答案(或信号),并非数据上的一个窗口。

06 / 去 LeetCode 上练习

四道题,按难度排序。前两题是数组压缩,后两题是链表的经典问题。

01Remove Duplicates from Sorted Array— LC 26简单→02Move Zeroes— LC 283简单→03Linked List Cycle— LC 141简单→04Middle of the Linked List— LC 876简单→

— / 什么时候用哪个

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