算法思想总结：双指针算法

一、移动零

. - 力扣（LeetCode） 移动零

该题重要信息：1、保持非0元素的相对位置。2、原地对数组进行操作

 思路：双指针算法

class Solution {
public:
    void moveZeroes(vector<int>& nums)
    {
         int n=nums.size();
         for(int cur=0,des=-1;cur<n;++cur)
               if(nums[cur])//如为非零，就要与des后面的位置元素进行交换
                  swap(nums[++des],nums[cur]);
    }
};

 二、复写零

. - 力扣（LeetCode）复写零

该题的重要信息：1、不要在超过该数组的长度的位置写入元素（就是不要越界）2、就地修改（就是不能创建新数组）。3、不返回任何东西。

 思路：双指针算法

class Solution {
public:
    void duplicateZeros(vector<int>& arr)
    {
        int cur=0,des=-1,n=arr.size();
        //找最后一个被复写数的位置
        for(;cur<n;++cur)
        {
            if(arr[cur])
            ++des;
            else
            des+=2;
            if(des>=n-1)//要让des指向最后一个位置
            break;
        }
        //边界修正
        if(des==n)
        {
            arr[--des]=0;
            --des;
            --cur;
        }
        //从后往前复写
        for(;cur>=0;--cur)
        {
            if(arr[cur])
            arr[des--]=arr[cur];
            else
            {
                arr[des--]=0;
                arr[des--]=0;
            }
        }
    }
};

 三、快乐数

. - 力扣（LeetCode）快乐数

 该题的关键是：将正整数变成他的每位数的平方之和，有可能会一直循环始终到不了1，也有始终是1（快乐数）

思路：快慢双指针算法

以上的两个结论在博主的关于链表带环追击问题的文章里面有分析

顺序表、链表相关OJ题（2）-CSDN博客

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(fast!=slow)
        {
            slow=bitsum(slow);
            fast=bitsum(bitsum(fast));
        }
        return slow==1;
    }
};

四、盛最多水的容器

. - 力扣（LeetCode）盛最多水的容器

思路1、暴力枚举（时间复杂度太高）

class Solution {
public:
    int maxArea(vector<int>& height)
    {
        //暴力枚举
        int n=height.size();
        int ret=0;
          for(int i=0;i<n;++i)
             for(int j=i+1;j<n;++j)
                   ret=max(ret,min(height[i],height[j])*(j-i));
        return ret;
    }
};

思路2、双指针对撞算法

class Solution {
public:
    int maxArea(vector<int>& height)
    {
      int left=0,right=height.size()-1,ret=0;
      while(left<right)
      {
           ret=max(ret,min(height[left],height[right])*(right-left));
           if(height[left]<height[right])
           ++left;
           else
           --right;
      }
          return ret;
    }
};

五、有效三角形的个数

. - 力扣（LeetCode）有效三角形的个数

 思路1：升序+暴力枚举

思路2：升序+利用双指针算法

class Solution {
public:
    int triangleNumber(vector<int>& nums) 
    {
        //排序一下
        sort(nums.begin(),nums.end());
        //先固定一个数，然后用双指针去找比较小的两个数
        int n=nums.size(),ret=0;
         for(int i=n-1;i>=2;--i)
         {
            int left=0,right=i-1;
            while(left<right)
            {
                int sum=nums[left]+nums[right];
                if(sum<=nums[i])  ++left;
                else  
                {
                    ret+=(right-left);
                    --right;
                } 
            }
         }
         return ret;
    }
};

 六、查找总价格为目标值的两个商品

. - 力扣（LeetCode）查找总价格为目标值的两个商品

 

思路1：两层for循环找到所有组合去计算

思路2：利用单调性，使用双指针算法解决问题

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

七、三数之和

. - 力扣（LeetCode）三数之和

解法1：排序+暴力枚举+set去重

解法2：排序+双指针

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        vector<vector<int>> ret;
        int n=nums.size();
        //先排序
        sort(nums.begin(),nums.end());
        //先固定一个数
        for(int i=0;i<n;)
        {
             if(nums[i]>0) break;//小优化
            int target =-nums[i];//目标值
            //定义双指针
            int left=i+1,right=n-1;
            while(left<right)
            {
                int sum=nums[left]+nums[right];
                if(sum<target)  ++left;
                else if(sum>target) --right;
                else  
                {
                   ret.push_back({nums[left],nums[right],nums[i]});//插入进去
                   ++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;
    }
};

八、四数之和

. - 力扣（LeetCode）四数之和

解法1：排序+暴力枚举+set去重

解法2：排序+双指针（和上一题基本一样，无非就是多固定了一个数）

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
       vector<vector<int>> ret;
       //先进行排序
       sort(nums.begin(),nums.end());
       //利用双指针解决
       int n=nums.size();
       //先固定一个数
       for(int i=0;i<n;)
       {
          //再固定一个数
          for(int j=i+1;j<n;)
          {
            int left=j+1,right=n-1;
            long long aim=(long long)target-nums[i]-nums[j];//确保不超出范围
            while(left<right)
            {
             long long sum=nums[left]+nums[right];
            if(sum<aim)  ++left;
            else if(sum>aim) --right;
            else 
            {
            ret.push_back({nums[i],nums[j],nums[left],nums[right]});
                ++left;
                --right;
                //去重
                while(left<right&&nums[left]==nums[left-1]) ++left;
                while(left<right&&nums[right]==nums[right+1]) --right;
            }
            }
             //去重
          ++j;
          while(j<n&&nums[j]==nums[j-1]) ++j;
          }
          //去重
          ++i;
          while(i<n&&nums[i]==nums[i-1]) ++i;
          }
          return ret;
    }
};

 九，接雨水

. - 力扣（LeetCode）接雨水

 思路：（正难则反）雨水的面积=总面积（每层面积相加）-柱子的面积（数组和）

 

时间复杂度：o(N) 

class Solution {
public:
    int trap(vector<int>& height) 
    {
       int n=height.size();
       if(n<3) return 0;//如果数组元素少于三个就没有必要去计算了
       int z=accumulate(height.begin(),height.end(),0);//计算z为柱子的总面积
       int sum=0;//用sum来统计总面积。
       int left=0,right=n-1;//定义双指针
       int prevh=0;//记录之前的高度
       while(left<right)
       {
        //让left和right同时超过之前的高度
         while(left<right&&height[left]<=prevh) ++left;
         while(left<right&&height[right]<=prevh) --right;
         //加上该层的面积
         sum+=(min(height[left],height[right])-prevh)*(right-left+1);
         //更新之前的高度
         prevh=min(height[left],height[right]);
       }
       return sum-z;//总面积-柱子面积就是雨水面积
    }
};

十、总结

常见的双指针有三种形式：前后指针、对撞指针、快慢指针

1、前后指针：用于顺序结构，一般是两个指针同方向，cur指针用来遍历数组，des指针将数组进行区域划分。（如1、2题）

       注意事项：如果是从前往后遍历，要注意dst不能走得太快，否则cur还没遍历到一些数就会被覆盖掉，必要时候可以根据情况从后往前遍历。

2、快慢指针：其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。
这种⽅法对于处理环形链表或数组⾮常有⽤。（如第3题，以及链表带环的问题）

        注意事项： 其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使⽤快慢指针的思想。最常用的就是快指针走两步，慢指针走一步。

3、对撞指针：一般用于顺序结构。从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。并且常常会用到单调性！！（如4-9题）
        注意事项：对撞指针的终⽌条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环）

用双指针策略一般可以比暴力枚举降低一个次方的时间复杂度

第9题还用到了正难则反的策略

     如果后面还有关双指针的经典题目，博主会继续在这篇更新的！！