【优选算法】不允许你还不会双指针
【优选算法】不允许你还不会双指针
移动零
针对这种数组分块、数组划分的问题，可以考虑使用双指针(前后双指针)思想进行划分。
代码实现
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;
}四数之和 <-- 此题是建立在三数之和完成后的类似题目
腾讯云开发者
