1. 双指针算法
在数据结构链表和顺序表的学习中，我们已经使用过双指针的算法思想。例如删除数组中的重复元素、判断链表是否为环、找出链表的中间节点等。
常见的双指针有两种形式，一种是对撞指针，一种是左右指针。
- 对撞指针：一般用于顺序结构中。一个指针从最左端开始，另一个从最右端开始，逐渐往中间逼近。终止条件一般是两个指针相遇（
left == right）或者错开（left > right）。- 快慢指针：又称为龟兔赛跑算法。基本思想是使用两个移动速度不同的指针在数组或链表等序列结构上移动。最常用的方式是在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位。这种方法对于处理环形链表或数组非常有用。
2. 双指针在算法题内的使用
2.1 移动零
题目解析
将数组内的所有零都移动到非零元素之后，并且保持所有非零元素的相对位置不变。
示例：输入 [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]);
}
}
}
};
2.2 复写零
题目解析
将数组中的每个 0 复写一遍，非 0 元素保持不变。要求就地实现，不能申请新内存空间。
算法原理讲解
正向遍历时，若直接复写会导致后续元素被覆盖。因此采用从后向前遍历的策略。
步骤：
- 初始化
cur = 0,dest = -1。 - 找到最后一个需要复写的数：遍历原数组，遇到 0 则
dest移两位，否则移一位。直到dest越界或到达末尾。 - 处理特殊情况：如果最后一个复写的数是 0 且导致
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--];
}
}
}
};
2.3 快乐数
题目解析
判断给定整数是否是快乐数。快乐数定义为不断替换成其各位数字平方之和，最后循环结果为 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;
}
};
2.4 盛水最多的容器
题目解析
找出能盛最多水的容器。容积 = 两边距离 × 短边高度。
算法原理讲解
暴力解法时间复杂度 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;
}
};
2.5 有效三角形的个数
题目解析
统计数组中能组成三角形的三元组个数。任意两边之和大于第三边。
算法原理讲解
暴力枚举 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;
}
};
2.6 和为 s 的两个数字
LCR 179. 查找总价格为目标值的两个商品 - LeetCode
题目解析
在升序数组中找出两数之和等于 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};
}
};
2.7 三数之和
题目解析
找出所有和为 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;
}
};
2.8 四数之和
题目解析
找出所有和为 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;
}
};