本文系统讲解双指针算法，涵盖对撞指针与快慢指针两种核心形式。通过移动零、复写零、快乐数、盛最多水的容器、有效三角形个数、两数之和、三数之和及四数之和八道经典题目，演示如何从暴力解法优化至双指针方案。文章提供 C++ 代码实现，涵盖数组操作、去重、溢出处理等关键细节，帮助读者掌握双指针在解决序列问题中的核心应用。
在数据结构链表和顺序表的学习中，我们已经使用过双指针的算法思想。例如删除数组中的重复元素、判断链表是否为环、找出链表的中间节点等。
常见的双指针有两种形式，一种是对撞指针，一种是左右指针。
left == right）或者错开（left > right）。将数组内的所有零都移动到非零元素之后，并且保持所有非零元素的相对位置不变。
示例：输入 [1,0,3,12]，输出 [1,3,12,0,0]。
该题属于数组分块类型，特征是将数组划分为几个区间。适合使用双指针解决。在数组中使用双指针时，指针通常用数组下标表示。
思路：
创建两个数组下标 cur 和 dest。cur 从左往右遍历数组，dest 指向已处理区间内的最后一个非零元素。数组可划分为三个区间：[0, dest]（非零）、[dest+1, src-1]（零）、[src, n-1]（待遍历）。最终当 src 遍历到末尾时，剩余部分补零。
流程：
cur 位置元素为 0 时，只让 cur++。cur 位置元素不为 0 时，先让 dest++，再交换 dest 和 cur 位置的元素。class Solution {
public:
void moveZeroes(vector<int>& nums) {
int dest = -1;
for(int src = 0; src < nums.size(); src++) {
if(nums[src] != 0 && ++dest != src) {
swap(nums[src], nums[dest]);
}
}
}
};
将数组中的每个 0 复写一遍，非 0 元素保持不变。要求就地实现，不能申请新内存空间。
正向遍历时，若直接复写会导致后续元素被覆盖。因此采用从后向前遍历的策略。
步骤：
cur = 0, dest = -1。dest 移两位，否则移一位。直到 dest 越界或到达末尾。dest 越界，需单独处理边界。cur 位置开始往前遍历，依次还原复写后的结果。class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int cur = 0, dest = -1;
while(cur < arr.size()) {
if(arr[cur] == 0) dest += 2;
else dest++;
if(dest >= arr.size() - 1) break;
cur++;
}
if(dest == arr.size()) {
arr[arr.size() - 1] = 0;
cur--;
dest -= 2;
}
while(cur >= 0) {
if(arr[cur] == 0) {
arr[dest--] = 0;
arr[dest--] = 0;
cur--;
} else {
arr[dest--] = arr[cur--];
}
}
}
};
判断给定整数是否是快乐数。快乐数定义为不断替换成其各位数字平方之和，最后循环结果为 1。
使用快慢指针检测循环。快指针每次走两步，慢指针每次走一步。若相遇且值为 1，则是快乐数；否则不是。
class Solution {
public:
int getsum(int n) {
int sum = 0;
while(n > 0) {
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
bool isHappy(int n) {
int fast = getsum(getsum(n));
int slow = getsum(n);
while(slow != fast) {
fast = getsum(getsum(fast));
slow = getsum(slow);
}
return slow == 1;
}
};
找出能盛最多水的容器。容积 = 两边距离 × 短边高度。
暴力解法时间复杂度 O(N^2)。优化方案使用双指针，初始分别指向首尾。每次移动较短的一边，因为移动较长边只会减小宽度且高度不会增加，容积必然减小。
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1, sum = 0;
while(left < right) {
int h = min(height[left], height[right]);
int len = right - left;
sum = max(h * len, sum);
if(height[left] < height[right]) left++;
else right--;
}
return sum;
}
};
统计数组中能组成三角形的三元组个数。任意两边之和大于第三边。
暴力枚举 O(N^3)。优化方法：先排序，固定最大边 i，使用双指针 left 和 right 寻找另外两边。若 nums[left] + nums[right] > nums[i]，则 left 到 right-1 的所有元素均满足条件。
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size(), sum = 0;
for(int i = 2; i < n; i++) {
int left = 0, right = i - 1;
while(left < right) {
if(nums[left] + nums[right] > nums[i]) {
sum += right - left;
right--;
} else {
left++;
}
}
}
return sum;
}
};
在升序数组中找出两数之和等于 target 的二元组。
使用双指针 left 和 right 分别指向首尾。根据当前和与 target 的大小关系移动指针。时间复杂度 O(N)。
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target) {
int n = price.size();
int left = 0, right = n - 1;
while(left < right) {
if(price[left] + price[right] > target) right--;
else if(price[left] + price[right] < target) left++;
else return {price[left], price[right]};
}
return {-1, -1};
}
};
找出所有和为 0 且不重复的三元组。
先排序，固定一个数 a，转化为两数之和问题。使用双指针在剩余区间查找。注意去重：跳过相同的 a、left 和 right。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> v;
int n = nums.size();
for(int i = 0; i < n - 2;) {
if(nums[i] > 0) break;
int left = i + 1, right = n - 1, sum = -nums[i];
while(left < right) {
if(nums[left] + nums[right] > sum) right--;
else if(nums[left] + nums[right] < sum) left++;
else {
v.push_back({nums[left], nums[right], nums[i]});
left++, right--;
while(left < right && nums[left] == nums[left - 1]) left++;
while(left < right && nums[right] == nums[right + 1]) right--;
}
}
i++;
while(i < n && nums[i] == nums[i - 1]) i++;
}
return v;
}
};
找出所有和为 target 且不重复的四元组。
类似三数之和，固定两个数，剩余部分使用双指针。注意数据类型溢出问题，求和时使用 long long。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
vector<vector<int>> v;
int n = nums.size();
for(int i = 0; i < n;) {
for(int j = i + 1; j < n;) {
long long count2 = (long long)target - nums[i] - nums[j];
int left = j + 1, right = n - 1;
while(left < right) {
int count1 = nums[left] + nums[right];
if(count1 > count2) right--;
else if(count1 < count2) left++;
else {
v.push_back({nums[left], nums[right], nums[i], nums[j]});
left++, right--;
while(left < right && nums[left] == nums[left - 1]) left++;
while(left < right && nums[right] == nums[right + 1]) right--;
}
}
j++;
while(j < n && nums[j] == nums[j - 1]) j++;
}
i++;
while(i < n && nums[i] == nums[i - 1]) i++;
}
return v;
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online