【算法】双指针算法
个人主页 ： zxctscl 如有转载请先通知
1. 283. 移动零
1.1 分析
一、题目分析 要将0放在所有数组的最后，而且非零元素的顺序保持不变，要求原地对数组进行移动。
二、算法原理 用两个指针来讲数组进行划分，一个cur：从左往右扫描数组，遍历数组；一个dest：已经处理的区间内，非零元素的最后一个位置。 就将数组分为3个区间：非零：[0,dest]；0区间：[dest+1,cur-1]；待处理的区间:[cur,n-1]. 要想这样划分，cur就得从前往后在遍历的过程中，遇到0元素，就加加；遇到非零元素，就将dest+1位置和cur位置的值交换。
1.2 代码
class Solution {
public:
void moveZeroes(vector<int>& nums) {
for(int cur=0,dest=-1;cur<nums.size();cur++)
{
if(nums[cur])
{
swap(nums[++dest],nums[cur]);
}
}
}
};2. 1089. 复写零
2.1 分析
一、题目解析 要求每次遇到0就复写，而且不能改变原数组的长度。
二、算法原理 如果用双指针从前往后遍历，就拿例1来说， 就会出现值被覆盖的情况：
所以遍历顺序就不能从前往后。 那么就把顺序改为从后往前遍历，但是不能超过原数组的长度，就得先找一下cur和dest开始的位置。 可以先用双指针算法：1.先判断cur位置；2.决定dest向后移动一步或者两步；3.判断一下dest是否已经到达结束位置；4.在把cur加加。 但是可能会出现dest越界的情况，如果n-1位置为0，那么cur就减减，dest就减2。 最后在从后往前开始复写0。
2.2 代码
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int cur=0,dest=-1;
int n=arr.size();
while(cur<n)
{
if(arr[cur])dest++;
else dest+=2;
if(dest>=n-1)break;
cur++;
}
if(dest==n)
{
arr[n-1]=0;
cur--;
dest-=2;
}
while(cur>=0)
{
if(arr[cur])arr[dest--]=arr[cur--];
else
{
arr[dest--]=0;
arr[dest--]=0;
cur--;
}
}
}
};3. 202. 快乐数
3.1 分析
一、题目分析 题目中所说最后的平方和为1才是快乐数，如果不为1，就一直循环，其实可以看成两个都是循环，一个一直循环的是1，另一个循环的值都不相同。只需要判断循环里面的值是不是为1就可以。
二、算法原理 先用一个变量sum记录最后平方和，然后把最后一位平方，然后删掉原来的数，一直重复这个过程，直到最后一位为0，最后返回这个平方和sum。
定义两个快慢指针，用平方和来充当指针，slow指向第一个数，fast指向第二个数，如果这两个指针一直不相等，就一直循环，slow走一步，fast走两步。直到两个相遇为止，等于1就是快乐数，不等于就不是。
3.2 代码
class Solution {
public:
int bitsum(int n)
{
int sum=0;
while(n)
{
int t=n%10;
sum+=t*t;
n/=10;
}
return sum;
}
bool isHappy(int n) {
int slow=n,fast=bitsum(n);
while(slow!=fast)
{
slow=bitsum(slow);
fast=bitsum(bitsum(fast));
}
return slow==1;
}
};4. 11. 盛最多水的容器
4.1 分析
一、题目分析 题目中的数组代表每一条线的高度，来求最大的容积，来看一下例1：
选择的高度是8和7，但是题目要求不能倾斜，这里选择高度的就是7，宽度就是下标之间的差值8-1也就是7，那么容积最大就是7*7=49。
二、算法原理 用两个指针来记录容器两边的高度，可以直接先选择最大的宽度，记录下这个容积。 如果左边指针走一步，宽度在减小，高度可能会出现比之前的小，那么体积就比原来的小；高度如果不变，那么宽度减小，那么总容积也是在减小的。所以得干掉高度小的那一个值。 如果两个指针指向的值相等，那么干掉谁都可以，然后继续枚举里面相乘的容积，直到两个指针相遇，最后返回容积最大的值就行。
4.2 代码
class Solution {
public:
int maxArea(vector<int>& height) {
int left=0,right=height.size()-1,v=0;
int ret=0;
while(left<right)
{
v=min(height[left],height[right])*(right-left);
ret=max(ret,v);
if(height[left]<height[right])left++;
else right--;
}
return ret;
}
};5. LCR 179. 查找总价格为目标值的两个商品
5.1 分析
一、题目分析 只需要找到两个数，他们的和等于目标值就可以，但是题目中的数组是按照升序排列的，暴力解法会超时，就不考虑了。
二、算法原理 利用数组是有序的，用双指针算法来算。 定义两个指针，一个在左边，一个在右边。 先计算两个指针指向值的和，判断一下和目标值的大小，会出现三种情况：1.小于目标值，那么左边指针就加加；2.等于就返回这两个值；3.大于目标值，那么右边指针就减减。
5.2 代码
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target) {
int left=0,right=price.size()-1,sum=0;
while(left<right)
{
sum=price[left]+price[right];
if(sum<target)left++;
else if(sum>target)right--;
else return{price[left],price[right]};
}
return {-1,-1};
}
};6. 15. 三数之和
6.1 分析
一、题目分析 题目要求返回三元数组和为1的三个不同的数，而且要求去重，来看一下例1： 它里面有[-1,0,1]、[0,1,-1]、[-1,2,-1]，但是第一组和第二组的元素是相同的，就只能返回一个。
为了避免去重，可以先给数组排个序。
二、算法原理 排序之后，数据是有序的，这里就用双指针算法。 这里是三个数的和，可以先固定一个数a，仅想要保证这个a是小于0就行（在后面等于0相加的值不可能等于0），然后在该数后面的区间内，利用双指针算法，快速找到两个数的和，者两个数的和是a的相反数，这样这三个数相加的时候，值就为0。 这里还有可能不止一种情况，所以不要漏掉，在找到一种情况时候，左边指针和右边指针继续缩小区间找，直到两个指针相同。 那么怎么去重，已经是有序的数组，那么连续相同值的情况就不考虑了，就是在左边指针和右边指针已经找到值，就跳过重复的值。当使用完重复的元素时候，固定值也得跳过重复值。还得避免越界的情况。
6.2 代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> ret;
int n=nums.size();
for(int i=0;i<n;)
{
if(nums[i]>0)break;
int left=i+1,right=n-1,target=-nums[i];
while(left<right)
{
int sum=nums[left]+nums[right];
if(sum<target) left++;
else if(sum>target)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<n&&nums[i]==nums[i-1])i++;
}
return ret;
}
};有问题请指出，大家一起进步！！！