【优选算法】不允许你还不会双指针

🌟 各位看官好，我是egoist2023！

🌍 种一棵树最好是十年前，其次是现在！

🚀 今天来学习双指针的相关用法

👍 如果觉得这篇文章有帮助，欢迎您一键三连，分享给更多人哦

目录

 移动零

代码实现

复写零

代码实现

快乐数

代码实现

盛最多水的容器

代码实现

有效三角形个数

代码实现

 移动零

针对这种数组分块、数组划分的问题，可以考虑使用双指针(前后双指针)思想进行划分。

代码实现

 void moveZeroes(vector& nums) { int left=-1,cur=0; while(cur<nums.size()) { if(nums[cur]!=0) swap(nums[++left],nums[cur]); cur++; } }

复写零

(错误)决策一：利用双指针从前向后遍历时往dest上填写会发现行不通，它会把之后的数覆盖。

因此我们只能考虑\"从后向前\"的策略完成复写。

决策二：\"从后向前\"复写

难点1：如何确定cur从哪里开始向前遍历？

难点2：是否含有边界情况？如何处理？

此类题是半模拟题，需要不断地画图总结。

定义cur指向下标为0的位置，dest指向-1，通过遍历cur并让其指向的值决定dest是走一步还是走两步，当dest>=n-1时即找到了cur的位置。

特殊情况：通过上述方法，处理情况2时会发现dest==n,因此需要把arr[n-1]=0,同时cur--,dest-=2。

代码实现

void duplicateZeros(vector& arr) { //确定cur的位置 int cur=0,dest=-1,n=arr.size(); while(cur=n-1) break; cur++; } //处理边界情况 if(dest==n) { arr[n-1]=0; cur--; dest-=2; } //\"从后向前\"复写 while(cur>=0) { if(arr[cur]==0) { arr[dest--]=0; arr[dest--]=0; } else arr[dest--]=arr[cur]; cur--; } }

快乐数

通过模拟n=19和2的情况，可以发现只会出现两种情况。

情况1：最后的值为1时是围绕1无限循环下去。

情况2：无限循环成环。

解决此类题目一般采用快慢双指针的解法 --> 快慢指针相遇时判断其值是否为1即可。

1.定义快慢指针fast和slow

2.fast每次走两步,slow每次走一步。

3.由于这两种情况都会成环，因此slow和fast最终会在环中相遇，判断相遇值即可。 

代码实现

bool isHappy(int n) { //快慢指针 int slow=n,fast=square(n); while(fast!=slow) { slow=square(slow); fast=square(fast); fast=square(fast); } if(fast==1) return true; else return false; } int square(int n) { int sum=0; while(n) { int ret=n%10; sum+=ret*ret; n/=10; } return sum; }

盛最多水的容器

方案一：我们可以遍历数组，将每一个能容量的水量都计算出来，最后用sort即可得出最终答案，但这样肯定会超时，因此需采用其他方案来解决。

方案二：定义left指向下标0位置，right指向下标n-1位置，利用双指针解决。

代码实现

int maxArea(vector& height) { int Max=INT_MIN; int left=0,right=height.size()-1; while(left<right) { int h=min(height[left],height[right]); Max=max(Max,h*(right-left)); if(height[left]<height[right]) left++; else right--; } return Max; }

有效三角形个数

解法：在数组有序的情况下，如果nums[left]+nums[right]<=sum ,根据单调性只有让left++才有可能使nums[left]+nums[right]>sum。

代码实现

int triangleNumber(vector& nums) { sort(nums.begin(),nums.end()); int n=nums.size(),tmp=n-1,size=0; while(tmp>1) { int left=0,right=tmp-1; while(leftnums[tmp]) {  size+=right-left;  right--; } else left++; } tmp--; } return size; }

三数之和 

四数之和

根据题意可知需返回所有和为0且下标不重复的三元组。

解法1：先进行排序(方便去重)，把每种情况都暴力枚举一遍， 然后利用库中的set去重，毋庸置疑，这个解法是会超时的。

解法2：当我们对数组排序后，这个数组就是一个单调的数组，那么利用双指针就可以解决此问题。

但是又如何把重复的三元组进行去重呢？

先left++，对left进行去重时，看看left指向元素是否与前面的一个元素相等，相等的话left继续++，直到不相等为止。同样需对right和i进行去重。

vector<vector> threeSum(vector& nums) { //1.排序 sort(nums.begin(),nums.end()); //2.双指针 vector<vector> ret; int n=nums.size(); for(int i=0;i<n-2;) { for(int j=i+1,k=n-1,flag=-nums[i];jflag) k--; else if(nums[j]+nums[k]<flag) j++; else {  ret.push_back({nums[i],nums[j],nums[k]});  //去重  j++,k--;  while(j<k&&nums[j-1]==nums[j]) j++;  while(j<k&&nums[k+1]==nums[k]) k--; } } //去重 i++; while(i<n&&nums[i]==nums[i-1]) i++; } return ret; }

四数之和 <-- 此题是建立在三数之和完成后的类似题目 

​