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

一、移动零

. - 力扣（LeetCode） 移动零

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

 思路：双指针算法

class Solution {
public:
    void moveZeroes(vector<int>& nums)
    {
         int n=nums.size();
         for(int cur=0,des=-1;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
        {
            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
             for(int j=i+1;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
      {
           ret=max(ret,min(height[left],height[right])*(right-left));
           if(height[left]
           ++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
            {
                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
           {
               int sum=price[left]+price[right];
               if(sum>target) --right;
               else if(sum
               else return {price[left],price[right]};
           }
           return {1,0};
    }
};

七、三数之和

. - 力扣（LeetCode）三数之和

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

解法2：排序+双指针

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

八、四数之和

. - 力扣（LeetCode）四数之和

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

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

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

九、总结

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

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

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

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

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

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

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

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