【优选算法】不允许你还不会双指针
🌟 各位看官好，我是egoist2023！
🌍 种一棵树最好是十年前，其次是现在！
🚀 今天来学习双指针的相关用法
👍 如果觉得这篇文章有帮助，欢迎您一键三连，分享给更多人哦
目录
移动零
针对这种数组分块、数组划分的问题，可以考虑使用双指针(前后双指针)思想进行划分。
代码实现
void moveZeroes(vector<int>& 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<int>& arr) { //确定cur的位置 int cur=0,dest=-1,n=arr.size(); while(cur<n) { //根据cur的值决定dest走一步还是两步 if(arr[cur]==0) dest+=2; else dest++; if(dest>=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<int>& 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<int>& 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(left<right) { if(nums[left]+nums[right]>nums[tmp]) { size+=right-left; right--; } else left++; } tmp--; } return size; }
根据题意可知需返回所有和为0且下标不重复的三元组。
解法1：先进行排序(方便去重)，把每种情况都暴力枚举一遍， 然后利用库中的set去重，毋庸置疑，这个解法是会超时的。
解法2：当我们对数组排序后，这个数组就是一个单调的数组，那么利用双指针就可以解决此问题。
但是又如何把重复的三元组进行去重呢？
先left++，对left进行去重时，看看left指向元素是否与前面的一个元素相等，相等的话left继续++，直到不相等为止。同样需对right和i进行去重。
vector<vector<int>> threeSum(vector<int>& nums) { //1.排序 sort(nums.begin(),nums.end()); //2.双指针 vector<vector<int>> ret; int n=nums.size(); for(int i=0;i<n-2;) { for(int j=i+1,k=n-1,flag=-nums[i];j<k;) { if(nums[j]+nums[k]>flag) 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; }四数之和 <-- 此题是建立在三数之和完成后的类似题目
