【算法笔记】双指针算法深度剖析

【算法笔记】双指针算法深度剖析

🔥个人主页：大白的编程日记

🔥专栏：算法笔记

前言

哈喽，各位小伙伴大家好！今天给大家分享的是入门算法双指针。算法我们程序员必备的技能。话不多说，咱们进入正题！向大厂冲锋！

一.移动零

1.1题目

• 题目：移动零
  

1.2思路分析

这里我们无非就是想让数组维持非0元素在前，0元素在后的区间状态。同时不改变非0元素的相对顺序。那我们可以用区间思想，借助双指针维护我们的区间状态。

1.3代码实现

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for(int cur=0,dest=-1;cur<nums.size();cur++)//初始化同时扫描数组
        {
            if(nums[cur])//判断是否非0
            {
                swap(nums[++dest],nums[cur]);//dest移动后交换
            }
        }
    }
};
//分成三个区间未处理区
//处理区分区为非0元素区和0元素区

二.复写零

2.1题目

• 题目：复写零
  

2.2思路分析

我们从左往右无法复写，因为会覆盖后面的数据。但是从右往左复写可以。所以我们找到最后一个复写的数，处理一下特殊情况从右往左复写即可。

2.3代码实现

class Solution {
public:
    void duplicateZeros(vector<int>& arr) 
    {
        int dest=-1,cur=0,n=arr.size();
        while(dest<n-1)//找到最后一个复写数
        {
            if(arr[cur]==0)
            {
                dest++;
            }
            dest++;
            if(dest>=n-1)
            {
                break;
            }
            cur++;
        }
        if(dest==n)//防止越界
        {
            arr[--dest]=0;
            dest--;
            cur--;
        }
        while(cur>=0)//从后往前复写
        {
            if(arr[cur]==0)
            {
                arr[dest--]=0;
                arr[dest--]=0;
                cur--;
            }
            else
            {
                arr[dest--]=arr[cur--];
            }
        }
    }
};

三.快乐数

3.1题目

• 题目：
  快乐数
  

3.2思路分析

这里我们根据鸽巢原理就可以把题目转化为判断入环点是否为1。
具体快慢指针相遇的问题可以看这篇 快慢指针相遇证明

3.3代码实现

这里我们用两个变量代替指针的作用。

class Solution {
public:
        int bitSum(int n)//计算每个数的平方和
        {
            int sum=0;
            while(n)
            {
                sum+=pow(n%10,2);
                n/=10;
            }
            return sum;
        }
        bool isHappy(int n) {
        int slow=bitSum(n);
        int fast=bitSum(slow);
        while(slow!=fast)
        {
            slow=bitSum(slow);
            fast=bitSum(fast);
            fast=bitSum(fast);
        }
        return slow==1;//判断入环点是否为1
    }
};

四.盛水最多的容器

4.1题目

• 题目：盛水最多的容器
  

4.2思路分析

这里我们需要观察规律解题。

4.3正确性证明

4.4代码实现

class Solution {
public:
        int maxArea(vector<int>& height)
        {
            int max=0;
            int left=0,right=height.size()-1;
            while(left<right)//双指针法
            {
            int v=fmin(height[left],height[right])*(right-left);//保存枚举的最大值
            max=fmax(v,max);//更新最大值
            height[left]<height[right]?left++:right--;
        }
        return max;
    }
};

五.有效三角形个数

5.1题目

• 题目：有效三角形的个数
  

5.2思路分析

这里我们用排序的单调性做优化.

正确性证明上一个题解有，这里就不过多赘述了。

5.3代码实现

class Solution {
public:
    int triangleNumber(vector<int>& nums) 
    {
      int ret=0;
      sort(nums.begin(),nums.end());
      for(int i=nums.size()-1;i>=2;i--)//固定最大的数
      {
          int left=0,right=i-1;
          while(left<right)
          {
              int t=nums[left]+nums[right];
              if(t>nums[i])//大于
              {
                ret+=(right-left);
                right--;
              }
              else//小于
              {
                left++;
              }
          }
       }
       return ret;
    }  
};

六.两数之和

6.1题目

• 题目：两数之和
  这里题目改了但是题意是一样的
  

6.2思路分析

这里依旧是按照单调性优化。

需要注意的是如果我们找到存在多个结果，我们找到结果后让left和right指针继续移动查找即可。

6.3代码实现

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        sort(nums.begin(),nums.end());//排序
        int left=0,right=nums.size()-1;
        while(left<right)
        {
            int tmp=nums[left]+nums[right];
            if(tmp<target)
            {
                left++;
            }
            else if(tmp>target)
            {
                right--;
            }
            else //找到结果
            {
                return {nums[left],nums[right]};
            }
        }
        return {};
    }
};

七.三数之和

7.1题目

• 题目：三数之和
  

7.2思路分析

这里我们可以转化为两数之和来解决问题。但是要注意去重的问题。

7.3代码实现

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        vector<vector<int>> ret;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size()-2;)//固定最左边的指针
        {
            if(nums[i]>0)//大于没结果
            {
                break;
            }
            int left=i+1,right=nums.size()-1;
            int target=-nums[i];//找两数之和
            while(left<right)//左右指针两数之和，先移动再比较
            {
                int tmp=nums[left]+nums[right];
                if(tmp<target)//小于
                {
                    left++;
                    while(left<right&&nums[left]==nums[left-1])//跳过重复元素去重
                    {
                        left++;
                    }
                }
                else if(tmp>target)//大于
                {
                    right--;
                    while(left<right&&nums[right]==nums[right+1])//跳过重复元素去重
                    {
                        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<nums.size()&&nums[i]==nums[i-1])//跳过重复元素去重
            {
                    i++;
            }
            //去重
        }
        return ret;
    }
};

八.算法总结

双指针算法总体来说就是利用两个指针，根据题目要求灵活结合单调性，区间思想，以及题目场景用指针的移动访问解决问题。总而言之，双指针需要根据题目灵活使用解决问题

后言

这就是双指针算法原理的深度剖析，这些题目基本包含了双指针的所有解题方法。大家自己好好消化。感谢大家的耐心垂阅！今天就分享到这，咱们下期见！拜拜~