双指针算法详解

目录

一、双指针

 二、双指针题目

 1.移动零

 解法：

代码：

 2.复写零

​编辑

 解法：

 代码：

边界情况处理:

 3.快乐数

​编辑

 解法:快慢指针

代码：

4.盛水最多的容器

 解法：（对撞指针）

代码： 

 5.有效三角形的个数

​编辑  

解法：

 代码：

6.和为s的两个数字

 解法：（对撞指针）

 代码：

7.三数之和

 解法：

 代码:

---

一、双指针

常⻅的双指针有两种形式，⼀种是对撞指针，⼀种是左右指针。

对撞指针：⼀般⽤于顺序结构中，也称左右指针。

1. 对撞指针从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。
2. 对撞指针的终⽌条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：

• left == right （两个指针指向同⼀个位置）
• left > right （两个指针错开）

快慢指针：⼜称为⻳兔赛跑算法，其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。

这种⽅法对于处理环形链表或数组⾮常有⽤。

其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使⽤快 慢指针的思想。

快慢指针的实现⽅式有很多种，最常⽤的⼀种就是：

• 在⼀次循环中，每次让慢的指针向后移动⼀位，⽽快的指针往后移动两位，实现⼀快⼀慢。

 二、双指针题目

 1.移动零

【数组分两块】是⾮常常⻅的⼀种题型，主要就是根据⼀种划分⽅式，将数组的内容分成左右两部

分。这种类型的题，⼀般就是使⽤「双指针」来解决。

 283. 移动零 - 力扣（LeetCode）

 解法：

两个指针：

• cur：从左到右扫描整个数组
• dest：已处理的数组中，非零元素的最后位置

代码：

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]);//交换，dest++}
};

 swap(nums[++dest], nums[cur])：这里的操作有两部分：

1. ++dest：先将 dest 指针向前移动一位。这个步骤确保了每当找到一个非零元素时，它会被放置到数组的前面，而 dest 会保持在下一个非零元素的位置。
2. swap(nums[dest], nums[cur])：将 cur 指向的非零元素与 dest 指向的元素交换位置。此时，cur 指向的非零元素被放到数组的前面，dest 也向前移动一位，以准备接收下一个非零元素。

 2.复写零

1089. 复写零 - 力扣（LeetCode）

 解法：

从后往前复写，大体流程分为两步：

1. 先找到最后一个复写的数
   先判断cur位置的值
   决定dest向后移动一步或者两步
   判断一下dest是否已经到结束为止
   cur++
2. 从后往前进行复写操作

 代码：

class Solution {
public:void duplicateZeros(vector<int>& arr) {//1.先找到最后一个数int cur=0,dest=-1,n=arr.size();while(cur<n){if(arr[cur]) dest++;//不等于0，走1步else dest+=2;//等于0，走两步if(dest >= n-1) break;cur++;}//2.处理一下边界情况（最后一个元素是0，需要复写两遍，会导致越界；）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--;}}}
};

边界情况处理:

如果越界：1.n-1位置的值修改成0；

                  2.cur向前移动一步

                  3.dest向前移动两步

 3.快乐数

 202. 快乐数 - 力扣（LeetCode）

 解法:快慢指针

【快慢指针】有⼀个特性，就是在⼀个圆圈中，快指针总是会追上慢指针的，也就是说他们总会相遇在⼀个位置上。如果相遇位置的值是 1 ，那么这个数⼀定是快乐数；如果相遇位置不是 1的话，那么就不是快乐

1. 定义快慢指针
2. 满指针每次向后移动一步，块指针每次向后移动两步
3. 判断相遇时候的值即可

 补充：求一个数n每个位置上的数组的平方和

1.把数 n 每⼀位的数提取出来：

        循环迭代下⾯步骤：

• int t = n % 10 提取个位；
• n /= 10 ⼲掉个位；

直到 n 的值变为 0 ；

2.提 取每⼀位的时候，⽤⼀个变量 tmp 记录这⼀位的平⽅与之前提取位数的平⽅和

• tmp = tmp + t * t

代码：

class Solution {
public:int Sum(int n){int sum=0;while(n){int t=n%10;sum+=t*t;n/=10;}return sum;}bool isHappy(int n) {//双指针，solw走一步，fast走两步int slow=n,fast=Sum(n);while(slow!=fast){slow=Sum(slow);fast=Sum(Sum(fast));}return slow==1;}
};

4.盛水最多的容器

 11. 盛最多水的容器 - 力扣（LeetCode）

 解法：（对撞指针）

设两个指针 left ， right 分别指向容器的左右两个端点，此时容器的容积 :

v = (right - left) * min( height[right], height[left])

容器的左边界为 height[left] ，右边界为 height[right] 。

为了⽅便叙述，我们假设「左边边界」⼩于「右边边界」。

如果此时我们固定⼀个边界，改变另⼀个边界，⽔的容积会有如下变化形式：

• 容器的宽度⼀定变⼩。
• 由于左边界较⼩，决定了⽔的⾼度。如果改变左边界，新的⽔⾯⾼度不确定，但是⼀定不会超 过右边的柱⼦⾼度，因此容器的容积可能会增⼤。
• 如果改变右边界，⽆论右边界移动到哪⾥，新的⽔⾯的⾼度⼀定不会超过左边界，也就是不会 超过现在的⽔⾯⾼度，但是由于容器的宽度减⼩，因此容器的容积⼀定会变⼩的。

由此可⻅，左边界和其余边界的组合情况都可以舍去。所以我们可以 left++ 跳过这个边界，继续去判断下⼀个左右边界。

当我们不断重复上述过程，每次都可以舍去⼤量不必要的枚举过程，直到 left 与 right 相

遇。期间产⽣的所有的容积⾥⾯的最⼤值，就是最终答案

代码： 

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;}
};

 5.有效三角形的个数

611. 有效三角形的个数 - 力扣（LeetCode）

  

解法：

先将数组排序

双指针法：

从 i = n-1 开始，遍历每个可能的第三条边（从最大的边开始）。然后使用两个指针 left 和 right，分别指向数组的起始和 i-1 位置。

• 如果 nums[left] + nums[right] > nums[i]，说明当前的 left 和 right 可以和 nums[i] 组成一个三角形，并且 [left, right-1] 之间的所有组合也满足条件。此时，结果增加 right - left。
• 如果不满足条件，说明 nums[left] 太小，无法与 nums[right] 和 nums[i] 组成三角形，需要增大 left。

 代码：

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int n=nums.size(),ret=0;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;//如果nums[left]+nums[right]>nums[i]说明[left,right-1]区间上的//所有元素均可以与nums[right]构成比nums[i]大的二元组//有right-left种right--;}else//nums[left] + nums[right] <= nums[i]说明left位置的元素是不可能与[left+1,right]位置上的元素构成满足条件的二元组{left++;}}}return ret;}
};

6.和为s的两个数字

 

 解法：（对撞指针）

1. 初始化左右指针：left = 0 和 right = price.size() - 1。left 指向数组的起始位置，right 指向数组的末尾位置。

2. 循环条件：while (left < right)。这表示只要 left 小于 right，就继续进行搜索。如果 left >= right，说明已经遍历完了所有可能的组合。

3. 计算当前和：int sum = price[left] + price[right]。计算当前指针所指向的两个元素的和。

4. 判断和的关系：

   • 如果和大于目标值：sum > target，说明当前两个数的和太大了，可以将 right 指针左移，减小和。
   • 如果和小于目标值：sum < target，说明当前两个数的和太小了，可以将 left 指针右移，增大和。
   • 如果和等于目标值：sum == target，找到目标和，直接返回这两个元素。

 代码：

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int left=0,right=price.size()-1;while(left<right){int sum=price[left]+price[right];if(sum>target) right--;//当 nums[left] + nums[right] > target 时,nums[right]与最小的数相加还大于target，剩下的也肯定大于，直接right--else if(sum<target) left++;//同理，当 nums[left] + nums[right] > target 时,直接left++else return {price[left],price[right]};}return {-1,-1};}
};

7.三数之和

15. 三数之和 - 力扣（LeetCode）

 解法：

利⽤在两数之和那⾥⽤的双指针思想：

• 先排序；
• 然后固定⼀个数 a ：
• 在这个数后⾯的区间内，使⽤「双指针算法」快速找到两个数之和等于 -a 即可。
• 但是要注意的是，这道题⾥⾯需要有「去重」操作
  1.找到⼀个结果之后， left 和 right 指针要「跳过重复」的元素；
  2.当使⽤完⼀次双指针算法之后，固定的 a 也要「跳过重复」的元素

 代码:

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;){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--;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 ret;}
};

感谢，再见