【算法笔记】双指针算法深度剖析

【算法笔记】双指针算法深度剖析

🔥个人主页：大白的编程日记

🔥专栏：算法笔记

---

前言

哈喽，各位小伙伴大家好！今天给大家分享的是入门算法双指针。算法我们程序员必备的技能。话不多说，咱们进入正题！向大厂冲锋！

一.移动零

1.1题目

• 题目：移动零
  

1.2思路分析

这里我们无非就是想让数组维持非0元素在前，0元素在后的区间状态。同时不改变非0元素的相对顺序。那我们可以用区间思想，借助双指针维护我们的区间状态。

1.3代码实现

class Solution {
public:void moveZeroes(vector<int>& nums) {for(int cur=0,dest=-1;cur<nums.size();cur++)//初始化同时扫描数组{if(nums[cur])//判断是否非0{swap(nums[++dest],nums[cur]);//dest移动后交换}}}
};
//分成三个区间未处理区
//处理区分区为非0元素区和0元素区

二.复写零

2.1题目

• 题目：复写零
  

2.2思路分析

我们从左往右无法复写，因为会覆盖后面的数据。但是从右往左复写可以。所以我们找到最后一个复写的数，处理一下特殊情况从右往左复写即可。

2.3代码实现

class Solution {
public:void duplicateZeros(vector<int>& arr) {int dest=-1,cur=0,n=arr.size();while(dest<n-1)//找到最后一个复写数{if(arr[cur]==0){dest++;}dest++;if(dest>=n-1){break;}cur++;}if(dest==n)//防止越界{arr[--dest]=0;dest--;cur--;}while(cur>=0)//从后往前复写{if(arr[cur]==0){arr[dest--]=0;arr[dest--]=0;cur--;}else{arr[dest--]=arr[cur--];}}}
};

三.快乐数

3.1题目

• 题目：
  快乐数
  

3.2思路分析

这里我们根据鸽巢原理就可以把题目转化为判断入环点是否为1。
具体快慢指针相遇的问题可以看这篇 快慢指针相遇证明

3.3代码实现

这里我们用两个变量代替指针的作用。

class Solution {
public:int bitSum(int n)//计算每个数的平方和{int sum=0;while(n){sum+=pow(n%10,2);n/=10;}return sum;}bool isHappy(int n) {int slow=bitSum(n);int fast=bitSum(slow);while(slow!=fast){slow=bitSum(slow);fast=bitSum(fast);fast=bitSum(fast);}return slow==1;//判断入环点是否为1}
};

四.盛水最多的容器

4.1题目

• 题目：盛水最多的容器
  

4.2思路分析

这里我们需要观察规律解题。

4.3正确性证明

4.4代码实现

class Solution {
public:int maxArea(vector<int>& height){int max=0;int left=0,right=height.size()-1;while(left<right)//双指针法{int v=fmin(height[left],height[right])*(right-left);//保存枚举的最大值max=fmax(v,max);//更新最大值height[left]<height[right]?left++:right--;}return max;}
};

五.有效三角形个数

5.1题目

• 题目：有效三角形的个数
  

5.2思路分析

这里我们用排序的单调性做优化.

正确性证明上一个题解有，这里就不过多赘述了。

5.3代码实现

class Solution {
public:int triangleNumber(vector<int>& nums) {int ret=0;sort(nums.begin(),nums.end());for(int i=nums.size()-1;i>=2;i--)//固定最大的数{int left=0,right=i-1;while(left<right){int t=nums[left]+nums[right];if(t>nums[i])//大于{ret+=(right-left);right--;}else//小于{left++;}}}return ret;}  
};

六.两数之和

6.1题目

• 题目：两数之和
  这里题目改了但是题意是一样的
  

6.2思路分析

这里依旧是按照单调性优化。

需要注意的是如果我们找到存在多个结果，我们找到结果后让left和right指针继续移动查找即可。

6.3代码实现

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {sort(nums.begin(),nums.end());//排序int left=0,right=nums.size()-1;while(left<right){int tmp=nums[left]+nums[right];if(tmp<target){left++;}else if(tmp>target){right--;}else //找到结果{return {nums[left],nums[right]};}}return {};}
};

七.三数之和

7.1题目

• 题目：三数之和
  

7.2思路分析

这里我们可以转化为两数之和来解决问题。但是要注意去重的问题。

7.3代码实现

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;sort(nums.begin(),nums.end());for(int i=0;i<nums.size()-2;)//固定最左边的指针{if(nums[i]>0)//大于没结果{break;}int left=i+1,right=nums.size()-1;int target=-nums[i];//找两数之和while(left<right)//左右指针两数之和，先移动再比较{int tmp=nums[left]+nums[right];if(tmp<target)//小于{left++;while(left<right&&nums[left]==nums[left-1])//跳过重复元素去重{left++;}}else if(tmp>target)//大于{right--;while(left<right&&nums[right]==nums[right+1])//跳过重复元素去重{right--;}}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<nums.size()&&nums[i]==nums[i-1])//跳过重复元素去重{i++;}//去重}return ret;}
};

八.算法总结

双指针算法总体来说就是利用两个指针，根据题目要求灵活结合单调性，区间思想，以及题目场景用指针的移动访问解决问题。总而言之，双指针需要根据题目灵活使用解决问题

后言

这就是双指针算法原理的深度剖析，这些题目基本包含了双指针的所有解题方法。大家自己好好消化。感谢大家的耐心垂阅！今天就分享到这，咱们下期见！拜拜~