算法刷题系列（十二）：双指针——让两个位置协同移动
算法刷题系列（十二）：双指针——让两个位置协同移动
链表需要沿引用逐个移动；数组则可以通过下标直接访问任意位置。双指针利用两个位置之间的关系，让它们按规则协同移动，常常能避免重复扫描。
本篇介绍两种常见模式：有序数组中的相向指针，以及链表中的快慢指针。我们用原创的“有序价格中找出总价为目标值的一对商品”作为主例，推导为何每次移动一端都不会漏掉答案，再用 Java 和 Python 实现。
一、双指针不是一种固定算法
“双指针”描述的是一种组织遍历的方式，而不是单一模板。常见模式有：
| 模式 | 指针关系 | 常见场景 |
|---|---|---|
| 相向指针 | 从两端向中间移动 | 有序数组配对、回文检查 |
| 同向指针 | 都从左向右，速度或职责不同 | 快慢指针、原地筛选 |
| 滑动窗口 | 左右指针围成连续区间 | 连续子数组或子串 |
选择模式前要先说明指针代表什么，以及每次移动后维持什么不变量。若只是放了两个索引，却没有基于题目性质缩小候选范围，并不能自动降低复杂度。
二、原创例子：有序价格中寻找目标和
有一组按升序排列的商品价格：
1
prices = [2, 4, 7, 9, 13, 18]
需要找两件不同商品，使总价为 16，并返回它们的下标。这里有序性很关键。
令：
left从数组开头开始；right从数组末尾开始；- 当前总和为
prices[left] + prices[right]。
每次比较当前和与目标值：
- 当前和太小：移动
left向右； - 当前和太大：移动
right向左； - 相等：找到答案。
手动推演
left | right | 当前价格 | 总和 | 操作 |
|---|---|---|---|---|
| 0 | 5 | 2 + 18 | 20 | 太大，right-- |
| 0 | 4 | 2 + 13 | 15 | 太小，left++ |
| 1 | 4 | 4 + 13 | 17 | 太大，right-- |
| 1 | 3 | 4 + 9 | 13 | 太小，left++ |
| 2 | 3 | 7 + 9 | 16 | 找到 |
答案下标为 [2, 3]。
三、为什么移动这一端是安全的？
这是相向双指针能够成立的关键。
当前和太小：移动左指针
假设 prices[left] + prices[right] < target。对当前 left 而言，数组中任何位于 right 左边的数都不大于 prices[right]，所以：
1
prices[left] + prices[k] <= prices[left] + prices[right] < target
其中 left < k < right。因此当前最左元素 prices[left] 不可能与剩余区间里的任何元素组成目标和，可以安全地把 left 向右移动。
当前和太大：移动右指针
若 prices[left] + prices[right] > target，对当前 right 而言，左侧剩余元素都不小于 prices[left]，因此：
1
prices[k] + prices[right] >= prices[left] + prices[right] > target
其中 left < k < right。所以当前最右元素不可能与剩余区间里的任何元素组成目标和，可以安全地把 right 向左移动。
每一步都排除至少一个不可能参与答案的元素，直到找到目标和或两个指针相遇。
四、Java 实现：返回一组下标
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.Optional;
public class TwoPointerPair {
public static Optional<int[]> findPair(int[] sorted, int target) {
if (sorted == null) {
throw new IllegalArgumentException("sorted must not be null");
}
int left = 0;
int right = sorted.length - 1;
while (left < right) {
long sum = (long) sorted[left] + sorted[right];
if (sum == target) {
return Optional.of(new int[] {left, right});
}
if (sum < target) {
left++;
} else {
right--;
}
}
return Optional.empty();
}
public static void main(String[] args) {
int[] prices = {2, 4, 7, 9, 13, 18};
int[] answer = findPair(prices, 16).orElseThrow();
System.out.println(answer[0] + ", " + answer[1]); // 2, 3
}
}
求和时先转成 long，避免两个 int 相加时溢出。方法返回 Optional<int[]>，明确表达“可能找不到答案”，而不是伪造一组默认下标。
五、Python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from __future__ import annotations
def find_pair(sorted_values: list[int], target: int) -> tuple[int, int] | None:
if sorted_values is None:
raise ValueError("sorted_values must not be None")
left = 0
right = len(sorted_values) - 1
while left < right:
total = sorted_values[left] + sorted_values[right]
if total == target:
return left, right
if total < target:
left += 1
else:
right -= 1
return None
values = [2, 4, 7, 9, 13, 18]
assert find_pair(values, 16) == (2, 3)
assert find_pair([1, 3, 5], 20) is None
assert find_pair([8], 16) is None
算法假设输入已经升序排列。如果输入无序，不能直接使用这套移动规则；可以先排序，但排序会改变原下标，需要根据需求保存原始下标或返回排序后位置。
六、复杂度与和哈希表的比较
左右指针只会向中间移动，每个元素最多被越过一次：
- 时间复杂度：
O(n)； - 额外空间复杂度：
O(1)。
与前面的哈希表方法对比：
| 方案 | 前提 | 时间 | 额外空间 | 是否保留原顺序 |
|---|---|---|---|---|
| 哈希表 | 无需排序 | 平均 O(n) | O(n) | 是 |
| 排序后双指针 | 可排序或输入已排序 | 排序加扫描，通常 O(n log n) | 取决于排序实现 | 可能改变 |
| 已排序双指针 | 输入已升序 | O(n) | O(1) | 是 |
若题目要求原数组位置且不能重排，哈希表往往更直接；若数组本来有序，或题目只要求数值组合，相向双指针通常更节省空间。
七、同向双指针：快慢指针的直觉
相向双指针利用两端有序关系；同向双指针通常让两个指针承担不同职责。
以链表判断是否有环为例：
slow每次走一步；fast每次走两步。
如果链表无环，fast 会先到达尾部；如果存在环，进入环后 fast 每轮相对 slow 多走一步，二者最终会在环内相遇。
这里的关键不变量不是“快指针永远领先”，而是进入环后，两者之间的环上距离每轮变化 1（按环长度取模），最终会变为 0。此模式适合在不额外使用集合记录所有节点的情况下检测环。
八、边界与易错点
- 忘记输入必须有序：总和太小/太大时移动哪一端，依赖升序性质。
- 使用
left <= right：题目要求两个不同元素时应使用left < right，避免同一元素被用两次。 - 总和溢出：固定宽度整数相加时，必要时先提升到更宽类型。
- 无序数组直接套模板：无序时指针移动没有单调性保证。
- 排序后下标含义改变：若需返回原始下标，要在排序前把值与原下标绑定。
- 存在重复值但题目要求唯一组合：找到一个答案与枚举全部不重复组合是不同任务，后者还需要跳过重复值。
- 快慢指针的终止条件写错：访问
fast.next前先确保fast非空。
九、双指针与滑动窗口的关系
滑动窗口也是双指针的一种常见形式：left 和 right 围成一个连续区间，右边界扩展窗口，左边界在条件不满足或满足特定目标时收缩。
区别在于，普通相向指针从两端向内缩小候选区间；滑动窗口通常同向移动，并持续维护窗口内统计量。后续会专门讲窗口何时能单调移动，以及负数等条件为什么可能破坏某些窗口策略。
小结
双指针的本质是利用指针之间的关系排除候选或维护区间。相向指针常依赖有序性；快慢指针利用速度差解决链表环等问题；滑动窗口则用同向指针维护连续区间。写代码前先说明每个指针的职责和移动依据，才能判断算法是否真的正确。
下一篇将把双指针用于“ N 数之和”一类组合问题，重点处理排序、剪枝和重复解。