算法——双指针专题

一、移动零

1.链接

283. 移动零 - 力扣（LeetCode）

2.描述

3.思路

双指针，一个指针指向头，一个指针用来遍历数组，将非零的值依次往前放

4.参考代码

class Solution {
public:
    void moveZeroes(vector<int>& nums) 
    {
        for(int i = 0,head = 0;i<nums.size();i++)
        {
            if(nums[i])
                swap(nums[head++],nums[i]);
        }
    }
};

二、复写零

1.链接

1089. 复写零 - 力扣（LeetCode）

2.描述

3.思路

比较容易想到的思路就是用cur去遍历数组，遇到0就0往后的数据整体后挪，但这种思路时间复杂度较高

这里提供一个更加高效的方法

1.先找到原数组中，最终会被复习的最后一个数字

先用指针不做任何操作的模拟一遍，从前往后的复写，一个指针cur用于遍历数组，一个指针dest用来找到最末尾会被复写的数字，但是，此时会有个问题，当最后一个数字为0时，会出现越界情况，因为0需要两个位置，cur指针会落到n的位置，此时需要对这种情况单独做一下处理

2.从后往前的复习

有了第一步的基础，此时的cur会落在数组末尾处，dest落在最后一个需要被复写的数字上，此时只需要从后往前的进行复写即可

4.参考代码

class Solution {
public:
    void duplicateZeros(vector<int>& arr) 
    {
        int cur = 0;
        int dest = -1;
        int n = arr.size();

        while(cur<n)
        {
            if(arr[cur] == 0)
            {
                dest+=2;
            }
            else
            {
                dest++;
            }
            if(dest >=n-1)
                break;
            cur++;
        }
        //对可能出现的特殊情况进行处理
        if(dest == n)
        {
            arr[--dest] = 0;
            cur--;
            dest--;
        }
        while(cur>=0)
        {
            if(arr[cur] == 0)
            {
                arr[dest--] = 0;
                arr[dest--] = 0; 
                cur--;
            }
            else
            {
                arr[dest--] = arr[cur--];
            }
        }
    }
};

三、快乐数

1.链接

202. 快乐数 - 力扣（LeetCode）

2.描述

3.思路

根据题意，我们可以通过画图发现，任意一个数的最终结果都会陷入两种循环：

1.true：1->1->1->... 

2.false：不同的数之间的死循环

证明：假设一个最大的数9999999999，它的平方和结果为9*9*10 = 810（实际没有那么大），我们可以认为当循环到810+1次时，一定会有重复的数字出现

此时，我们使用快慢指针去让一个指针跑得快，一个指针跑得慢一点，那么若是在一个循环中，则快指针一定会在某时刻追上慢指针，此时只需要判断该循环时上面情况的哪种即可

4.参考代码

class Solution {
public:

    int happynum(int n)
    {
        int ret = 0;
        while(n)
        {
            int m = n%10;
            ret += m*m;
            n/=10;
        }
        return ret;
    }
    bool isHappy(int n) 
    {
        int fast = happynum(n);
        int slow = n;
        while(fast != slow)
        {
            fast = happynum(happynum(fast));
            slow = happynum(slow);
        }
        return fast == 1;
    }

四、盛水最多的容器

1.链接

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

2.描述

3.思路

根据题目分析，要确定容积，首先我们想到的就是暴力求解，将每一个情况都穷举遍历一遍

capacity = min[ height [left] ，height [right] ] *（right - left）

但时间复杂度太高，我们可以通过对撞指针的方式，去减少不必要的枚举

分析可知，让left指针和right指针分别置于左右两边，当一边小于另一边时，我们挪动大的那一边往中间靠，容积高度不变（高度取决于小的那一边），而宽度变小，容积一定变小，所以将大的一边往中间靠的操作没有任何意义

因此，只需要每次都将小的那一边往中间靠，宽缩小，但高有可能增大，容积也会增大，直到两个指针相遇，此时在这些情况中取最大值就是最大容积

4.参考代码

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

五、有效三角形的个数

1.链接

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

2.描述

3.思路

直接考虑，我们想到的就是三层for循环去穷举去所有的可能，在此思路下，我们尝试优化一下

我们知道三角形的两个最小的边之和一定会大于第三边，满足这个条件即可，因此，我们可以先给数组进行排序，然后设置一个所谓的最长边，然后然后用双指针去锁定最长边的前边部分

依次遍历数组中每个元素，即可求得一共有多少个有效三角形

4.参考代码

class Solution {
public:
    int triangleNumber(vector<int>& nums) 
    {
        int n = nums.size();
        if(n < 3)
        {
            return 0;
        }
        sort(nums.begin(),nums.end());
        int ret = 0;
        for(int i = 2;i<n;i++)
        {
            int left = 0;
            int right = i-1;
            while(left < right)
            {
                if(nums[left]+nums[right] <= nums[i])
                {
                    left++;
                }
                else
                {
                    ret+=right-left;
                    right--;
                }
            }
        }
        return ret;
    }
};

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

1.链接

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

2.描述

3.思路

不难想到，对撞指针，两个指针一左一右，相加值小于目标值则左边指针往右走，反之右边的往左走，直到找到相等的时刻返回即可，当两个指针相遇则没有满足条件的两个数

4.参考代码

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

七、三数之和

1.链接

15. 三数之和 - 力扣（LeetCode）

2.描述

3.思路

4.参考代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        int n = nums.size();
        int cur = 0;
        sort(nums.begin(),nums.end());
        vector<vector<int>> ret;
        while(cur < n)
        {
            int left = cur+1;
            int right = n-1;
            int x = -nums[cur];
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum < x)
                {
                    left++;
                }    
                else if (sum > x)
                {
                    right--;
                }
                else
                {
                    ret.push_back({nums[cur],nums[left++],nums[right--]});
                    //去重
                    while(left < right && nums[left] == nums[left-1])
                        left++;
                    while(left < right && nums[right] == nums[right+1])
                        right--;
                }
            }
            cur++;
            while(cur < n && nums[cur] == nums[cur-1]) cur++;
        }
        return ret;
    }
};

八、四数之和

1.链接

18. 四数之和 - 力扣（LeetCode）

2.描述

3.思路

思路和三数之和的思路是一样的，我们可以先固定一个数a，然后将其后面的部分用三数之和的思路去解决，找到target-a的值，思路上不难，但细节上需要有很多需要处理

关键在于去重有四个位置：

1.left和right找到后，需要对这两个去进行去重

2.当nums[ j ]找完往后走时需要去重

3.当nums[ i ]找完往后走时需要去重

4.参考代码

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        int n = nums.size();
        vector<vector<int>> ret;
        sort(nums.begin(),nums.end());
        for(int i = 0 ;i<n;)//先固定住一个数，然后后面的位置进行三数之和的思路去找到target-nums[i]
        {
            for(int j = i+1 ; j<n;)
            {
                int left = j+1;
                int right = n-1;
                while(left < right)//找到target-nums[i] - nums[j]的两数之和
                {
                    long long sum = (long long)nums[left] + (long long)nums[right];
                    long long des = (long long)target - nums[i] - nums[j];
                    if(sum < des)
                    {
                        left++;
                    }
                    else if(sum > des)
                    {
                        right--;
                    }
                    else
                    {
                        ret.push_back({nums[i],nums[j],nums[left++],nums[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;
    }
};

5.代码分析

总结

本篇总结了部分经典的关于双指针的算法题，其中有“对撞指针”“快慢指针”等等的思想和例题