双指针
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 / 常见坑
在无序数据上贸然使用。
没有顺序,移动指针就无法单调地改变候选值。 先排序,否则这就不是合适的工具。
while left < right 的差一错误。需要两个不同下标的配对时用
<;仅当同一个下标也可以独立满足关系时(罕见)才用 <=。忘记跳过重复值。
对于 3Sum 这类问题,命中之后可能需要在两侧分别跳过相等的相邻元素, 否则下一次迭代会重复输出同一对。
06 / 去 LeetCode 上练习
简单15
01Palindrome Number— LC 9→02Remove Duplicates from Sorted Array— LC 26→03Remove Element— LC 27→04Merge Sorted Array— LC 88→05Valid Palindrome— LC 125→06Palindrome Linked List— LC 234→07Move Zeroes— LC 283→08Reverse String— LC 344→09Reverse Vowels of a String— LC 345→10Is Subsequence— LC 392→11Valid Palindrome II— LC 680→12Sort Array By Parity— LC 905→13Sort Array By Parity II— LC 922→14Squares of a Sorted Array— LC 977→15Two Sum Less Than K— LC 1099→
中等18
01Longest Palindromic Substring— LC 5→02Container With Most Water— LC 11→033Sum— LC 15→043Sum Closest— LC 16→054Sum— LC 18→06Sort Colors— LC 75→07Remove Duplicates from Sorted Array II— LC 80→08Two Sum II - Input Array Is Sorted— LC 167→093Sum Smaller— LC 259→10Longest Word in Dictionary through Deleting— LC 524→11K-diff Pairs in an Array— LC 532→12Shortest Unsorted Continuous Subarray— LC 581→13Valid Triangle Number— LC 611→14Advantage Shuffle— LC 870→153Sum With Multiplicity— LC 923→16Max Number of K-Sum Pairs— LC 1679→17Maximum Distance Between a Pair of Values— LC 1855→18Maximum Tastiness of Candy Basket— LC 2517→
— / 什么时候用哪个
对向
当数组已排序且答案是一对时使用。
两数之和 · 回文 · 容器
快 / 慢
用于原地修改或环的检测。
去重 · 链表环
滑动窗口
当条件围绕一段连续区间时使用。
最长/最短 · 至多 k