《双指针算法指南：LeetCode 经典题解（C++实现）》
·
《双指针算法指南：LeetCode 经典题解（C++实现）》
—— 从快慢指针到对撞指针，刷题效率提升 200%！
常⻅的双指针有两种形式，⼀种是对撞指针，⼀种是左右指针。
对撞指针：
⼀般⽤于顺序结构中，也称左右指针。
-
对撞指针从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。
-
对撞指针的终⽌条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：
left == right （两个指针指向同⼀个位置）
left > right （两个指针错开）
快慢指针：
又称为龟兔赛跑算法，其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。
这种⽅法对于处理环形链表或数组⾮常有⽤。
其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使⽤快慢指针的思想。快慢指针的实现⽅式有很多种，最常⽤的⼀种就是：
• 在⼀次循环中，每次让慢的指针向后移动⼀位，⽽快的指针往后移动两位，实现⼀快⼀慢。
移动零（easy）
「数组分两块」是⾮常常⻅的⼀种题型，主要就是根据⼀种划分⽅式，将数组的内容分成左右两部分。这种类型的题，⼀般就是使⽤「双指针」来解决。
题⽬链接：
要点：
- 保持非零元素的相对顺序
- 空间复杂度需为 O(1)
- 通过双指针将数组分为已处理区（非零）和未处理区
老师代码：
class Solution
{
public:
void moveZeroes(vector<int>& nums)
{
for(int cur = 0, dest = -1; cur < nums.size(); cur++)
if(nums[cur]) // 处理⾮零元素
swap(nums[++dest], nums[cur]);
}
}
老师思路：
- 「数组分两块」是⾮常常⻅的⼀种题型，主要就是根据⼀种划分⽅式，将数组的内容分成左右两部分。这种类型的题，⼀般就是使⽤「双指针」来解决
- 在本题中，我们可以⽤⼀个 cur 指针来扫描整个数组，另⼀个 dest 指针⽤来记录⾮零数序列的最后⼀个位置。根据 cur 在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。 在 cur 遍历期间，使 [0, dest] 的元素全部都是⾮零元素， [dest + 1, cur - 1] 的元素全是零
我的代码：
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int dest = -1;//指向已经移动完成的区域的最后一个位置
int cur = 0;//指向当前需要操作的位置
while(cur < nums.size())
{
if(nums[cur] == 0)
{
cur++;
}
else
{
std::swap(nums[dest + 1], nums[cur]);
dest++;
cur++;
}
}
}
};
我的思路：
使用 dest 指针标记已处理非零元素的末尾，cur 指针遍历数组。当 cur 遇到非零元素时，与 dest+1 位置交换，dest 后移。此操作保证 [0, dest] 始终为非零元素，时间复杂度 O(n)。
我的笔记：
-
dest初始化为 -1，巧妙处理初始边界 -
交换操作后只需
dest++，无需重复检查已处理区域 -
对比老师的代码，发现
for循环比while更简洁，但逻辑等价
复写零
题⽬链接：
要点：
- 原地修改数组
- 从后向前复写避免覆盖未处理数据
- 需处理连续零导致数组越界的情况
老师代码：
class Solution
{
public:
void duplicateZeros(vector<int>& arr)
{
// 1. 先找到最后⼀个数
int cur = 0, dest = -1, n = arr.size();
while(cur < n)
{
if(arr[cur]) dest++;
else dest += 2;
if(dest >= n - 1) break;
cur++;
}
// 2. 处理⼀下边界情况
if(dest == n)
{
arr[n - 1] = 0;
cur--; dest -=2;
}
// 3. 从后向前完成复写操作
while(cur >= 0)
{
if(arr[cur]) arr[dest--] = arr[cur--];
else
{
arr[dest--] = 0;
arr[dest--] = 0;
cur--;
}
}
}
}
老师思路：
如果「从前向后」进⾏原地复写操作的话，由于 0 的出现会复写两次，导致没有复写的数「被覆盖掉」。因此我们选择「从后往前」的复写策略。但是「从后向前」复写的时候，我们需要找到「最后⼀个复写的数」，因此我们的⼤体流程分两步：i. 先找到最后⼀个复写的数；ii. 然后从后向前进⾏复写操作
我的代码：
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int dest = -1, cur = 0, n = arr.size();
while(cur < n)//用快慢双指针来找到最后一个可以复写到的元素，标记为cur
{
if(arr[cur]) dest++;
else dest +=2;
if(dest >= n - 1) break;
cur++;
}
if(dest == n)//如果dest出现越界，则cur指向的位置一定是0
{
arr[n - 1] = 0;//复写后的最后一个数字为0
dest -= 2;//回退到n-2
cur--;//回退一格
}
while(cur >= 0)//从后往前遍历复写
{
if(arr[cur]) arr[dest--] = arr[cur--];
else
{
arr[dest--] = 0;
arr[dest--] = 0;
cur--;
}
}
}
};
我的思路：
- 模拟填充：先用快慢指针找到最后一个有效元素的位置
- 边界修正：若模拟填充时
dest越界，需手动处理末尾零 - 逆向复写：从后往前填充，遇到零则复写两次
我的笔记：
- 注意边界情况
dest的移动规则：遇到非零+1，遇到零+2- 逆向复写时，
cur指针的起始位置需通过模拟填充确定 - 边界条件
dest == n表示最后一个有效元素是零且导致越界
快乐数
题⽬链接：
要点：
- 无限循环的两种形式：循环到1或在其他数循环
- 快慢指针可检测循环存在
老师代码：
class Solution
{
public:
int bitSum(int n) // 返回 n 这个数每⼀位上的平⽅和
{
int sum = 0;
while(n)
{
int t = n % 10;
sum += t * t;
n /= 10;
}
return sum;
}
bool isHappy(int n)
{
int slow = n, fast = bitSum(n);
while(slow != fast)
{
slow = bitSum(slow);
fast = bitSum(bitSum(fast));
}
return slow == 1;
}
}
老师思路：
为了⽅便叙述，将「对于⼀个正整数，每⼀次将该数替换为它每个位置上的数字的平⽅和」这⼀个操作记为 x 操作； 题⽬告诉我们，当我们不断重复 x 操作的时候，计算⼀定会「死循环」，死的⽅式有两种：
▪ 情况⼀：⼀直在 1 中死循环，即 1 -> 1 -> 1 -> 1…
▪ 情况⼆：在历史的数据中死循环，但始终变不到 1 由于上述两种情况只会出现⼀种，因此，只要我们能确定循环是在「情况⼀」中进⾏，还是在「情况⼆」中进⾏，就能得到结果。
简单证明：a. 经过⼀次变化之后的最⼤值 9^2 * 10 = 810 ( 2^31-1=2147483647 。选⼀个更⼤的最⼤ 9999999999 )，也就是变化的区间在 [1, 810] 之间； b. 根据「鸽巢原理」，⼀个数变化 811 次之后，必然会形成⼀个循环； c. 因此，变化的过程最终会⾛到⼀个圈⾥⾯，因此可以⽤「快慢指针」来解决
根据上述的题⽬分析，我们可以知道，当重复执⾏ x 的时候，数据会陷⼊到⼀个「循环」之中。 ⽽「快慢指针」有⼀个特性，就是在⼀个圆圈中，快指针总是会追上慢指针的，也就是说他们总会相遇在⼀个位置上。如果相遇位置的值是 1 ，那么这个数⼀定是快乐数；如果相遇位置不是 1 的话，那么就不是快乐数
我的代码：
class Solution {
public:
int fun(int x)
{
int a = 1, sum = 0;
while(x / a >= 10)
{
sum += (x % (a * 10) / a) * (x % (a * 10) / a);
a *= 10;
}
sum += (x / a) * (x / a);
return sum;
}
bool isHappy(int n) {
int fast = n, slow = n;
do
{
fast = fun(fast);
fast = fun(fast);
slow = fun(slow);
}while(fast != slow);
if(fast == 1) return true;
else return false;
}
};
我的思路：
- 定义
fast和slow指针，fast每次计算两次平方和，slow一次 - 若两指针相遇且值为1，则是快乐数；否则存在非1循环
我的笔记：
-
要学会老师取一个整数的每一位数的方法
-
简化代码
-
当提到无限循环的时候就要想到能不能用快慢双指针的方法解决问题，就像链表成环问题一样
-
平方和函数可用取余法优化：
while(n) { t = n%10; sum += t*t; n /=10; } -
快慢指针相遇后只需判断是否为1，无需继续计算
-
时间复杂度从 O(n) 降至 O(logn)
盛水最多的容器
题⽬链接：
要点：
- 容积公式：
min(height[left], height[right]) * (right - left) - 移动较短指针可能获得更大容积
老师代码：
class Solution
{
public:
int maxArea(vector<int>& height)
{
int left = 0, right = height.size() - 1, ret = 0;
while(left < right)
{
int v = min(height[left], height[right]) * (right - left);
ret = max(ret, v);
// 移动指针
if(height[left] < height[right]) left++;
else right--;
}
return ret;
}
}
老师思路：
我的代码：
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1;
int max = 0, maxi = 0;
while(left < right)
{
maxi = (right - left) * (height[left] < height[right] ? height[left] : height[right]);
max = max > maxi ? max : maxi;
if(height[left] < height[right])
{
left++;
}
else
{
right--;
}
}
return max;
}
};
我的思路：
从两端往中间靠拢的过程中，长度一直在减少，因此要想找到比现在还大的容积只有当高度比现在指针指向的高度还要高的情况才有可能出现，因此才有了上面的判断条件
我的笔记：
- 使用函数max() 和min()
- 贪心思想的典型应用
- 即使移动后高度可能降低，但宽度减少的损失已被提前计算
- 时间复杂度 O(n)，优于暴力法的 O(n²)
有效三角形个数
题⽬链接：
要点：
- 三角形判定：两边之和大于第三边
- 排序后固定最大边，双指针找有效组合
老师代码：
class Solution
{
public:
int triangleNumber(vector<int>& nums)
{
// 1. 优化
sort(nums.begin(), nums.end());
// 2. 利⽤双指针解决问题
int ret = 0, n = nums.size();
for(int i = n - 1; i >= 2; i--) // 先固定最⼤的数
{
// 利⽤双指针快速统计符合要求的三元组的个数
int left = 0, right = i - 1;
while(left < right)
{
if(nums[left] + nums[right] > nums[i])
{
ret += right - left;
right--;
}
else
{
left++;
}
}
}
return ret;
}
};
老师思路：
我的代码：
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int num = 0;
int hight = nums.size() - 1, left = 0, right = hight - 1;
while(hight >= 2)
{
while(left < right)
{
if(nums[left] + nums[right] > nums[hight])
{
num += right - left;
right--;
}
else
{
left++;
}
}
hight--;
left = 0, right = hight - 1;
}
return num;
}
};
我的思路：
- 排序数组，逆序枚举最大边
nums[i] - 双指针
left=0和right=i-1搜索满足nums[left] + nums[right] > nums[i]的组合 - 若满足条件，则
right-left个组合均有效
我的笔记：
- 排序算法，已经使用模版了，所以只需要使用模版中的排序算法就行了
- 排序时间复杂度 O(nlogn) 主导整体效率
- 双指针将内层循环从 O(n²) 优化到 O(n)
- 关键代码逻辑：
if (sum > target) ret += right - left;
和为 s 的两个数字
题⽬链接：
要点：
老师代码：
class Solution
{
public:
vector<int> twoSum(vector<int>& nums, int target)
{
int left = 0, right = nums.size() - 1;
while(left < right)
{
int sum = nums[left] + nums[right];
if(sum > target) right--;
else if(sum < target) left++;
else return {nums[left], nums[right]};
}
// 照顾编译器
return {-4941, -1};
}
}
我的代码：
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target) {
//vector<int> nums = {0, 0};
int left = 0, right = price.size() - 1;
while(left < right)
{
if(price[left] + price[right] == target)
{
//nums[0] = price[left], nums[1] = price[right];
return {price[left], price[right]};
}
else if(price[left] + price[right] > target)
{
right--;
}
else
{
left++;
}
}
//return nums;
return {0, 0};
}
};
我的思路：
我的笔记：
- 这里使用了一个大括号的隐式类型转换
三数之和
题⽬链接：
要点：
- 去重是关键：固定数、左指针、右指针均需跳过重复值
- 排序后使用双指针将时间复杂度从 O(n³) 降至 O(n²)
老师代码：
class Solution
{
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
vector<vector<int>> ret;
// 1. 排序
sort(nums.begin(), nums.end());
// 2. 利⽤双指针解决问题
int n = nums.size();
for(int i = 0; i < n; ) // 固定数 a
{
if(nums[i] > 0) break; // ⼩优化
int left = i + 1, right = n - 1, target = -nums[i];
while(left < right)
{
int sum = nums[left] + nums[right];
if(sum > target) right--;
else if(sum < target) left++;
else
{
ret.push_back({nums[i], nums[left], nums[right]});
left++, right--;
// 去重操作 left 和 right
while(left < right && nums[left] == nums[left - 1]) left++;
while(left < right && nums[right] == nums[right + 1]) right--;
}
}
// 去重 i
i++;
while(i < n && nums[i] == nums[i - 1]) i++;
}
return ret;
}
};
我的代码：
错误一
#include <vector>
class Solution {
private:
vector<vector<int>> arr;
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int heigh = nums.size() - 1, left = 0, right = heigh - 1;
while(heigh >= 2)
{
while(left < right)
{
if(nums[left] + nums[right] + nums[heigh] > 0)
{
while(right - 1 > 0 && nums[right - 1] == nums[right])
{
right--;
}
right--;
}
else if(nums[left] + nums[right] + nums[heigh] < 0)
{
while(left + 1 < heigh && nums[left + 1] == nums[left])
{
left++;
}
left++;
}
else
{
arr.push_back({nums[left], nums[right], nums[heigh]});
left++, right--;
}
}
left = 0, right = heigh - 1;
while(heigh >= 2 && nums[heigh - 1] == nums[heigh])
heigh--;
heigh--;
}
return arr;
}
};
错误二：
class Solution {
private:
vector<vector<int>> arr;
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
for(int a = 0; a < nums.size();)
{
int left = a + 1, right = nums.size() - 1;
while(left < right)
{
if(nums[left] + nums[right] + nums[a] == 0)
{
arr.push_back({nums[a], nums[left], nums[right]});
left++;//这里同样需要判断是否越界，这是错误原因
right--;
}
else if(nums[left] + nums[right] + nums[a] > 0)
{
right--;
while(left < right && nums[right + 1] == nums[right]) right--;//这段代码写到上面批注部分
}
else
{
left++;
while(left < right && nums[left - 1] == nums[left]) left++;//这段代码也写到上面批注部分
}
}
a++;
while(a < nums.size() && nums[a - 1] == nums[a]) a++;
}
return arr;
}
};
我的思路：
要点：
-
算法思：双指针思想
先排序
然后固定⼀个数 a
在这个数后⾯的区间内，使⽤「双指针算法」快速找到两个数之和等于 -a 即可 (这一条只要满足题意都可以)
-
注意：
找到⼀个结果之后， left 和 right 指针要「跳过重复」的元素；
使⽤完⼀次双指针算法之后，固定的 a 也要「跳过重复」的元素
越界判断
-
固定第一个数
nums[i]，转化为两数之和问题 -
双指针
left=i+1和right=n-1搜索target = -nums[i] -
去重操作需在找到解后立即执行
我的笔记：
-
我提交的代码是有一些无法通过的，其实就是边界问题没有处理好,如：
while(left < right && nums[right - 1] == nums[right])//这里是吧现在这个nums[right]，与数组的下一个nums[right - 1]对比 { right--; } right--;//如果使用这一种方法，这一条代码执行后就不能判断right是否越界了将这一串代码的判断条件换一个方法：
right--; while(left < right && nums[right + 1] == nums[right])//这里是吧现在这个nums[right]，与数组的上一个nums[right + 1]对比 { right--; }就可以完美解决无法判断后面right–;是否越界的情况
-
注意去重与越界访问问题，以后写代码都要记得考虑一下这个问题
-
去重代码模板：
while (i < n && nums[i] == nums[i-1]) i++; // 外层去重 while (left < right && nums[left] == nums[left-1]) left++; // 内层去重 -
边界检查
left < right必须放在条件首位，防止越界
四数之和
题⽬链接：
要点：
- 在三数之和基础上增加一层循环
- 使用
long long防止整数溢出
老师代码：
class Solution
{
public:
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
vector<vector<int>> ret;
// 1. 排序
sort(nums.begin(), nums.end());
// 2. 利⽤双指针解决问题
int n = nums.size();
for(int i = 0; i < n; ) // 固定数 a
{
// 利⽤ 三数之和
for(int j = i + 1; j < n; ) // 固定数 b
{
// 双指针
int left = j + 1, right = n - 1;
long long aim = (long long)target - nums[i] - nums[j];
while(left < right)
{
int sum = nums[left] + nums[right];
if(sum < aim) left++;
else if(sum > aim) right--;
else
{
ret.push_back({nums[i], nums[j], nums[left++],
nums[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 ret;
}
};
我的代码：
class Solution {
private:
vector<vector<int>> arr;
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size();)
{
for(int j = i + 1; j < nums.size();)
{
int left = j + 1, right = nums.size() - 1;
while(left < right)
{
long long num = (long long)nums[i] + nums[j] + nums[left] + nums[right];
if(num == target)
{
arr.push_back({nums[i], nums[j], nums[left], nums[right]});
left++, right--;
//去重一
while(left < right && nums[left] == nums[left - 1]) left++;
while(left < right && nums[right] == nums[right + 1]) right--;
}
else if(num > target) right--;
else left++;
}
//去重二
j++;
while(j <nums.size() && nums[j] == nums[j - 1]) j++;
}
//去重三
i++;
while(i < nums.size() && nums[i] == nums[i - 1]) i++;
}
return arr;
}
};
我的思路：
- 双重循环固定前两个数
nums[i]和nums[j] - 双指针
left=j+1和right=n-1搜索剩余两数- 每层循环均需去重
我的笔记：
- 去重：与前面的三数之和是一样的，去重时要考虑边界问题
- 边界问题：不去重的时候也要注意边界问题
- 这个题目在计算时会有数据溢出的风险，因此代码中用到了long long，此时在计算时算式的右边第一个变量也要强转成long long 类型
- 溢出处理：
long long aim = (long long)target - nums[i] - nums[j]; - 去重逻辑与三数之和一致，需在每层循环后跳过重复值
- 时间复杂度 O(n³)，但实际运行效率较高
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
14
0- 0
已为社区贡献2条内容
所有评论(0)