双指针

01 / 共享的机制

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

02 / 一句话本质
当输入有序、答案是一对满足某种关系的元素时, 将指针放在两端,根据比较结果移动错误的那一侧 — 每一次移动都是被比较所决定的。
题目找出满足 arr[i] + arr[j] = target 的 i, j输入[1, 2, 4, 7, 11, 15]目标9
10
21
42
73
114
155
输入有序,目标 9。将 left 置于开头,right 置于末尾。
步
0 / 8
L · R
—
arr[L] + arr[R]
—
与目标对比
—
0 / 8

03 / 模式骨架

# 一条有序序列上的两个下标left ← 0right ← n − 1while left < right:// 比较后决定移动哪一侧if arr[left] + arr[right] = target:return (left, right)elif sum < target:left++ // 需要更大的和else:right-- // 需要更小的和

04 / 什么时候用这个模式

"有序"
输入已经有序,或可以以较小代价排序。 有序性才让每一次移动都是确定的。
"一对"
答案恰好涉及两个元素 — 求和、求差,或一次匹配。
"回文 / 镜像"
数据具有可验证的对称结构,例如从两端向内逐个比较字符。
"最接近"
目标是最小化距离而不是精确匹配 — 在收敛过程中持续记录最优的一对。

05 / 常见坑

i.
在无序数据上贸然使用。
没有顺序,移动指针就无法单调地改变候选值。 先排序,否则这就不是合适的工具。
ii.
while left < right 的差一错误。
需要两个不同下标的配对时用 <;仅当同一个下标也可以独立满足关系时(罕见)才用 <=。
iii.
忘记跳过重复值。
对于 3Sum 这类问题,命中之后可能需要在两侧分别跳过相等的相邻元素, 否则下一次迭代会重复输出同一对。

06 / 去 LeetCode 上练习

四道题,按难度排序。前三题需要有序输入;第四题在可排序的输入上检验这一模式。

01Two Sum II — Input Array Is Sorted— LC 167中等→02Valid Palindrome— LC 125简单→03Container With Most Water— LC 11中等→043Sum— LC 15中等→

— / 什么时候用哪个

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