双指针通过两个索引变量在数组中协同移动，常用于有序数组的元素查找。其主要形式包括对撞指针（从两端向中间移动）、快慢指针（同向移动）和滑动窗口（一固定一滑动）。在查找两数之和时，利用对撞指针可在O(n)时间内找到目标值，避免暴力枚举的O(n²)复杂度。对于三数之和问题，先排序，再固定一个数，剩余部分使用双指针查找两数之和，将总时间复杂度优化至O(n²)，并需跳过重复元素以去重。该技巧适用于有序数组中的和查找、去重、合并数组、滑动窗口及链表环检测等问题，关键在于利用顺序性减少无效比较，但要求数组有序或配合其他结构如哈希表使用。
在C++中，双指针是一种高效处理数组或链表问题的技巧，尤其适用于有序数组中的元素查找。它通过两个指针从不同位置同时遍历，减少时间复杂度，避免暴力枚举。
双指针的基本思想
双指针不是真的指针变量，而是两个用于遍历数组的索引变量。它们可以：
- 从两端向中间移动（对撞指针）
- 一快一慢同向移动（快慢指针）
- 一个固定，另一个滑动（滑动窗口）
对于查找元素类问题，最常用的是对撞指针，特别是在有序数组中查找两数之和等于目标值的情况。
在有序数组中查找两数之和
假设有一个升序排列的数组，要找出两个数，使其和等于给定目标值。使用双指针可以从数组两端开始逼近：
立即学习“C++免费学习笔记（深入）”；
#include <iostream>
#include <vector>
using namespace std;
<p>pair<int, int> findTwoSum(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;</p><pre class='brush:php;toolbar:false;'>while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return {left, right}; // 返回下标
} else if (sum < target) {
left++; // 和太小，左指针右移
} else {
right--; // 和太大，右指针左移
}
}
return {-1, -1}; // 未找到}
这个方法的时间复杂度是 O(n)，比暴力 O(n²) 快很多，且不需要额外哈希表空间。
查找三数之和（进阶技巧）
三数之和问题也可以用双指针优化。基本思路是：
- 先排序数组
- 固定第一个数，然后对剩余部分使用双指针查找两数之和
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
<pre class='brush:php;toolbar:false;'>for (int i = 0; i < nums.size(); i++) {
// 跳过重复元素
if (i > 0 && nums[i] == nums[i-1]) continue;
int left = i + 1, right = nums.size() - 1;
int target = -nums[i];
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
result.push_back({nums[i], nums[left], nums[right]});
// 跳过相同值
while (left < right && nums[left] == nums[left+1]) left++;
while (left < right && nums[right] == nums[right-1]) right--;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return result;}
这种技巧将三重循环优化为 O(n²)，核心在于排序后利用有序性进行双指针搜索。
常见应用场景与注意事项
双指针适合以下场景：
- 有序数组中查找和为特定值的元素对
- 去重、合并有序数组
- 滑动窗口求最短/最长子数组
- 链表中判断环或找中点
注意点：
- 数组通常需要先排序
- 注意跳过重复元素以避免重复结果
- 边界条件如 left < right 不能漏掉
- 双指针不适用于无序数组的任意查找（除非配合哈希）
基本上就这些。掌握双指针的关键是理解“如何利用顺序关系减少无效比较”。在刷题中多练习两数之和、三数之和、盛最多水的容器这类经典题目，就能熟练运用这一技巧。
