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

一、移动零

. - 力扣（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;
    }
};