双指针算法(题目与答案讲解)

题目

力扣

移动零

1、移动零:题目链接

复写零

2、复写零:题目链接

两数之和

3、两数之和题目链接

N数之和(>2个数)

4、N数之和(三个数、四个数·····)
三个数:题目链接
四个数题目链接

答案讲解

移动零

思路

移动零：这个题目是利用双指针算法
双指针不一定是用2个指针，可以是下标或者值来代替
拿案例1来讲
让一个left指向-1 这个位置
让一个right指向0 这个位置
让right 走 如果right下标的数不为0
那么left++， swap(nums[left],nums[right])
让right继续走 如果遇到0 那么 left不动 那么left的下一个数必定为0
交换完之后 0就会到后面去

代码

class Solution {
public:void moveZeroes(vector<int>& nums) {int cur = 0;int dest = -1;while(cur<nums.size()){if(nums[cur]!=0){dest++;swap(nums[cur],nums[dest]);}cur++;}}
};

复写零

思路

复写零
同样也是用双指针
先找到要复写之后最后一个数
这么找？
用下标 一个定义cur为0 dest为-1
cur和dest同时++
如果cur下标的数为0
那么dest多++一次
如果dest走到最后一个元素那么就结束
cur位置就是最后复写的数
但是有一个小细节
因为如果最后一个要复写的数(cur位置为size-2的位置)并且为0
那么dest可能越界
所以要判断一下dest是否会越界
如果是这个情况
让数组最后一个数置为0
另一个0 因为越界了所以不用管
并且让cur–，dest-=2
这样子他们就不会越界了
找到需要复写的数下标cur之后
从后往前遍历
把cur下标位置的值赋值到dest位置下
如果cur下标位置为0
那么就让dest位置++2次并且复写2次0

代码：

class Solution {
public:void duplicateZeros(vector<int>& arr) {vector<int> s;int cur =0;int dest = -1;while(cur<arr.size()){if(arr[cur]){dest++;}else{dest+=2;}if(dest>=arr.size()-1){break;}cur++;}if(dest==arr.size()){arr[arr.size()-1]=0;cur--;dest-=2;}while(cur>=0){if(arr[cur]){arr[dest--]=arr[cur--];}else{arr[dest--]=arr[cur];arr[dest--]=arr[cur];cur--;}}}
};

两数之和

思路

同样是双指针算法
这个是升序的数组
定义一个下标为0的left和一个数组长度-1的数right
还有定义一个vector 用来接受最后的2个数
用下标left的数+下标为right的数 = 一个数
如果这个数大于target
那么吧right-- 因为是升序把大的干掉
如果小于
把left++ 把小的干掉

代码 :

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {vector<int> s;int left = 0,right = price.size()-1;while(left<right){if(price[left]+price[right]>target){right--;}else if(price[left]+price[right]<target){left++;}else{s.push_back(price[left]);s.push_back(price[right]);break;}}return s;      }
};

N数之和

三个数
题目解析:

要3个数相加=0 并且不能重复

思路

因为要找出三个数的和为0
优质解法是双指针
先定一个i让i指向下标为0这个数
然后在[1,nums.size()-1]中定义一个left 指向i+1这个位置 right 指向 size()-1这个位置
让一个数（B）接收 i下标位置的数并改成 他的相反数
这有一个小细节：如果 i下标位置>0那么 他后面的数都不用算了，因为>0的数相加肯定大于0
然后让一个数来接受left下标和right下标的数的和
如果这个和大于B 那么把大的干掉
如果小于 那么把小的干掉
找到之后吧他插入到vector中 然后left++ ，right–
去重(★)
如果left 位置和他的前一个位置 left-1的值相同 那么就++
因为如果 相同那么都判断过了 他插入也是插入重复的
题目不要重复的 所以直接++，一直++到不重复的为止
right也是一样 不过right是判断和他+1位置的值，如果相等那么–

四个数就是定2个数然后再后面的区间找

代码:

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());//排序吧数组变成有序vector<vector<int>> arr;for(int i = 0;i<nums.size();){int left = i+1,right = nums.size()-1;int a = -nums[i];if(nums[i]>0){//如果大于0 那么就说明后面的都是正数 正数+正数！= 比他们两个小的正数break;}while(left<right){if(nums[left]+nums[right]>a){right--;}else if(nums[left]+nums[right]<a){left++;}else{//{}扩起来的内容会形成一个vector 的数组扔到里面arr.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--;}}}//对nums[i]这个位置去重i++;while(i<nums.size() &&nums[i]==nums[i-1]){i++;}}return arr;      }
};