← 目录 / 算法文档 · 模块七 双指针与二分查找 / 7.1 双指针

7.1　双指针

用两个下标在数组上协同移动，往往能把一层嵌套循环"拆"掉，从 O(n²) 降到 O(n)。

本页目录
① 什么是双指针

双指针是指在数组（或字符串）上同时维护两个下标，让它们按照某种规则协同移动，一次遍历就能完成原本需要嵌套循环才能做的事。常见的用法有两种：对撞指针——一个从最左边出发，一个从最右边出发，两边向中间靠拢；快慢指针——两个指针同方向移动，但移动的速度或条件不一样。

② 对撞指针：有序数组两数之和

经典问题：给一个已经排好序的数组，找出其中两个数，使它们的和正好等于目标值。暴力做法是双层循环，枚举所有的两数组合，时间复杂度 O(n²)。

利用数组"已经排好序"这个性质，可以用对撞指针把它优化到 O(n)：left 指向最左边，right 指向最右边，看两者之和与目标值的关系——和太小，说明需要换一个更大的数，只能把 left 往右移；和太大，说明需要换一个更小的数，只能把 right 往左移；正好相等，就是答案。

C++ · 对撞指针求两数之和
1pair<int, int> TwoSumSorted(vector<int> arr, int target)
2{
3 int left = 0, right = arr.size() - 1;
4 while (left < right)
5 {
6 int sum = arr[left] + arr[right];
7 if (sum == target)
8 {
9 return {left, right};
10 }
11 else if (sum < target)
12 {
13 left++; // 和太小，换一个更大的数
14 }
15 else
16 {
17 right--; // 和太大，换一个更小的数
18 }
19 }
20 return {-1, -1}; // 没找到
21}
⚠️
为什么"和太小就移 left，和太大就移 right"是安全的，不会漏掉答案？假设当前 arr[left]+arr[right] 太小了——因为数组是有序的，arr[right] 已经是 right 这一侧能选到的最大值，如果连这个最大值配上 arr[left] 都不够大，那 arr[left] 配上 right 左边那些更小的数，结果只会更小——所以"arr[left] 配任何 ≤right 的数"这条路已经彻底走不通了，left 必须往右换成更大的数。同理，right 太大时，arr[right] 配任何 ≥left 的数也都行不通，只能把 right 往左移。
{2, 4, 7, 11, 15, 18, 22}，目标和 18 —— 对撞指针执行过程
left=0(值2), right=6(值22)，和=24，太大，right左移
2
4
7
11
15
18
22
left=0(值2), right=5(值18)，和=20，太大，right左移
2
4
7
11
15
18
22
left=0(值2), right=4(值15)，和=17，太小，left右移
2
4
7
11
15
18
22
left=1(值4), right=4(值15)，和=19，太大，right左移
2
4
7
11
15
18
22
left=1(值4), right=3(值11)，和=15，太小，left右移
2
4
7
11
15
18
22
left=2(值7), right=3(值11)，和=18，找到！
2
4
7
11
15
18
22
只用了 6 次比较就找到了答案（7+11=18），暴力双层循环最坏情况要比较 12 次。两个指针一共最多移动 n 次（left 只会前进、right 只会后退，加起来不会超过数组长度），所以整体是严格的 O(n)。
③ 快慢指针：去除有序数组的重复项

另一种常见用法是快慢指针——两个指针同方向移动，但角色不同：fast 负责"探路"，把数组从头到尾扫一遍；slow 负责"占坑"，记录"目前已经处理好、不重复的部分"应该写到哪个位置。经典场景：给一个已经排好序的数组，原地去掉所有重复的元素，只保留每个数值一份。

C++ · 快慢指针去除有序数组重复项
1int RemoveDuplicates(vector<int>& arr)
2{
3 if (arr.empty()) return 0;
4 int slow = 0; // slow指向"已确认不重复区域"的最后一个位置
5 for (int fast = 1; fast < arr.size(); fast++)
6 {
7 if (arr[fast] != arr[slow]) // fast发现了一个新值
8 {
9 slow++;
10 arr[slow] = arr[fast]; // 把新值"占坑"写到slow的位置
11 }
12 }
13 return slow + 1; // 去重后的新长度
14}
{1, 1, 2, 2, 2, 3, 4, 4, 5} —— 快慢指针去重过程
fastarr[fast]arr[slow]是否新值操作
111否，相同跳过
221是，不同slow→1，arr[1]=2
322否，相同跳过
422否，相同跳过
532是，不同slow→2，arr[2]=3
643是，不同slow→3，arr[3]=4
744否，相同跳过
854是，不同slow→4，arr[4]=5
最终 slow=4，去重后数组：{1, 2, 3, 4, 5}，长度 5
fast 像探路者一样一格不漏地往前走，slow 只在"发现新值"的时候才往前挪一格——挪动的那一刻，顺便把新值写到 slow 现在的位置上，相当于把不重复的数字一个个"搬"到数组前面，整个过程不需要额外的数组空间，原地完成。
④ 完整代码与对比
类型移动规则典型应用
对撞指针从两端向中间靠拢有序数组两数之和、判断回文、反转数组
快慢指针同方向移动，速度或触发条件不同原地去重、移除特定元素、链表找环
🎯
双指针能生效的前提，往往是数据具备某种单调性（比如本节两个例子都依赖"数组已经排好序"）——正是这种单调性，才能保证"指针只往一个方向移动、不需要回头"，从而把原本 O(n²) 的嵌套枚举，压缩成 O(n) 的一次遍历。这个思路和 6.1、6.2 节"利用单调性提前排除不可能的选项"是同一套逻辑，只是用指针代替了栈和队列。