基础算法--双指针算法

什么是双指针算法

通常我们讲的双指针就是用两个指针，两个指针可以是快慢指针，解决成环的问题，也可以是指向收尾的两个指针，来减小时间复杂度。双指针算法里的指针也不止是指针，在数组中也可以是数组元素的下标，这里双指针是一种思想，并不是单单指的是指针。
接下来我们用几道例题来看看双指针算法。

例题

1.移动零

题目：移动零

样例输出输入：

这道题要我们将所有零移到数组的末尾并且不改变数组的的非零元素的相对位置，并且有一个前提就是不能开辟新的数组，对原数组进行操作。
解法一：暴力解法
思路：两层循环，一层循环找零，一层循环移动零到最后一个零的位置。
解法二：双指针
思路：首先对于上面这个题可以这样理解，可以把他划分为两个大区间，一个已经排除过零的区间和一个未排除过零的区间，已排除过零的区间又可以划分为非零区间和一个只含零的区间所以这三个区间。

所以我们可以用一个指针指向非零与零的区间的分界线，再用一个指针对数组进行遍历，如果遇到零就继续++，因为零本来就该在最后，如果遇到非零数就交换非零区间和零区间的分解线的数，这里分界线取的是第一个零的位置。这样，当我们遍历到最后一个数之后，未划分区间就没有了，只剩下非零区间和零区间了。
代码展示：

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int cur=0;
        int dest=-1;
        while(cur<nums.size())
        {
            if(nums[cur]!=0)
            {
                swap(nums[cur],nums[dest+1]);
                dest++;
                cur++;
            }
            else
            {
                cur++;
            }
        }
    }
};

2.复写零

题目：复写零

样例输入输出：

题目的意思就是让我们把数组当中的零在零之后复写但是复写之后数组的长度不变，所以后面数向后移动，所以最后就得到了样例输出。

思路：
首先我们先用异地操作模拟一下，开辟一个新的数组，然后进行拷贝，用两个指针，一个指针对原来的数组进行遍历，一个指针对新开辟的数组进行遍历，如果原来的数组遇到非零先判断新开辟数组是否越界，然后进行拷贝，两个指针同时向后移动，如果遇到零的话，还是先判断新开辟的数组是否越界，如果越界就停止，如果没越界拷贝在新开辟的数组中拷贝两个零，新开辟数组的指针向后移动两个单位，原来的数组向后移动一个单位。
上面讲的是异地操作，我们将异地操作优化为就地操作，首先我们考虑数组从左向右复写，首先这是不可能的，一个数组遍历一个数组进行复写的话会导致当我们复写的到零的时候后面的数已经被零覆盖了，所以遍历的时候后面会一直是零，复写就会一直复写零，所以这里我们考虑数组从后往前复写，如果从后往前复写的话我们就要考虑复写的最终位置，这里想到第一个办法就是双指针先就地模拟一遍异地操作，如果遇到零就+=2，如果遇到非零就+=1，这样用两个指针，最后一个指向末尾的元素就是就是需要拷贝的位置，另一个指针进行遍历数组并没有指向最后一个位置，所以这个位置指向的是复写的最后一个位置。通过模拟异地的复写我们已经找到最后一个复写的位置，现在只需要倒着复写即可，遇到零则复写两边，遇到非零则复写一遍。
代码展示：

class Solution
{
public:
    void duplicateZeros(vector<int>& arr) 
    {
        //先找到最后一个复写位置，模拟异地操作
        int dest=-1;
        int cur=0;
        int n=arr.size();
        while(dest<n)
        {
            if(arr[cur]!=0)
            {
                dest++;
            }
            else
            {
                dest+=2;
            }
            if(dest>=n-1)break;
            cur++;
        }
        if(dest==n)
        {
            arr[n-1]=0;
            dest-=2;
            cur-=1;
        }
        //从后向前完成复写操作
        while(cur>=0)
        {
            if(arr[cur]!=0)
            {
                arr[dest--]=arr[cur--];
            }
            else
            {
                arr[dest]=arr[cur];
                arr[dest-1]=arr[cur];
                dest-=2;
                cur-=1;
            }
        }
    }
};

3.快乐数

题目：快乐数

样例输入输出：

解法：
首先我们来看看什么事快乐数，如果各个位的平方相加，通过一系列重复操作之后，最后结果变为1，这就是快乐数，注意上面一句话很重要也就是无限循环，但可能不是1，这句话很重要。
首先我们用上面给出的两个例子来做样例：

上图上面样例的两个例子这样一看我们也就很熟悉了，这不是我们在链表做的链表带环的问题吗？判断链表是否带环只需要用一个快慢指针，如果两个指针，最后相遇则证明有环，如果两个指针没有相遇则证明最后没有环，这道题也很类似，这里的指针只需要抽象成操作的步骤，慢指针只操作一步，快指针操作两步，上面两种情况肯定是有环的，所以我们只需要判断两个指针相遇时的数是否是1，如果是1，则返回true，如果不是1，则返回false。

代码展示：

class Solution {
public:
    //返回n这个数每一位上的平方和
    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;//slow等于第一个数
        int fast=bitsum(n);//fast等于第二个数
        while(fast!=slow)
        {
            fast=bitsum(bitsum(fast));
            slow=bitsum(slow);
        }
        return slow==1;
    }
};

4.盛最多水的容器

题目：

样例输入输出：

题目意思很简单，这里的数组中的每个值代表的是高度，然后每个值对应的下标之差表示的是容器的宽度，宽度*高度就是我们水的最大容积。

解法一：暴力解法
暴力解法很简单，我们只需要用两个for循环每次for循环都记录一下这次的最大的容积，然后每次for循环完了之后，都对之前的容器的大小进行比较，如果新的容积大则更新容积，如果新的容积小，则不动。
解法二：双指针算法
首先我们先取首尾的指针，用下面的图讲解一下原理：

所以根据这个原理，向内取的话肯定是减小，所以这里我们每次肯定是小的高度进行–或者++。这里我们需要的变量就是两个首尾指针，然后还有一个记录最小值，最小值表示高度，因为高度是最小值决定的，因为向内取v是在不断减小的，所以这里我们每次更新的时候需要更新高度小的那个，更新高度大的那个会出现的情况可以看上面的图。
代码展示：

class Solution {
public:
    //时间复杂度是O(N)
    int maxArea(vector<int>& height) {
        int tail=height.size()-1;
        int head=0;
        int v=0;
        while(head<tail)
        {
            int Min=min(height[head],height[tail]);
            if(v<Min*(tail-head))
            {
                v=Min*(tail-head);
            }
            if(height[tail]<height[head])
            {
                tail--;
            }
            else
            {
                head++;
            }
        }
        return v;
    }
};

5.有效三角形的个数

题目：

输出输入样例：

解法一：暴力解法
这道题的暴力解法就是就是逐个遍历，将每一种情况遍历一遍，这道题由于不用去重，所以复杂程度直线下降，所以我们直接用三角形的判定的公式直接逐个情况判断就可以了，这里可以套三层循环，每种情况进行遍历，然后如果成立的话可以直接用一个count进行记录三角形成立的个数
解法二：双指针
步骤1：进行排序。
步骤2：排序之后，我们可以先固定最大的数，这里我们知道三角形满足a+b>c，这里c是最大的数，所以我们可以先固定最大的数，由于我们排序之后最大的数是最后一个数，所以这里我们可以直接取最后一个数为c，然后从c前面的数中取出a和b，但是a和b不是乱取的，我们先取最大的和最小的，也就是c前面的一个和第一个，如果最大的和最小的都能组成三角形，那么中间的组合肯定能组成三角形，因为中间的任何一个都比最小的大，所以这里可以直接计算三角形的个数的情况，三角形个数就是下标之差，接下来还有两种情况就是a+b==c或者a+b 代码展示：

class Solution 
{
public:
    int triangleNumber(vector<int>& nums) 
    {
        sort(nums.begin(),nums.end());
        int count=0;
        int left=0;
        int right=nums.size()-2;
        int c=nums.size()-1;
        while(c>=2)
        {
            while(left<right)
            {
                if(nums[left]+nums[right]>nums[c])
                {
                    count+=(right-left);
                    right--;
                }
                else
                {
                    left++;
                }
            }
            //更新right和left
            c--;
            left=0;
            right=c-1;
        }
        return count;
    }
};

6.三数之和

题目：

样例输出和输入：

这里我们可以直接看样例，题目的大概意思就是我们需要从数组中找三元组，并且三元组满足三元组的每个成员都是原数组中的不同位置的数，并且三元组不能有重复，三元组还要满足一个条件就是三元组之和加起来等于0。
解法一：暴力解法
这道题的难点就是在去重上，所以这道题我们可以用三个循环，然后把每个元素都遍历一遍用一个vector存储，最后把这个vector存在vectorvector中，如果是去重的话，我们可以直接用C++的一个容器就是unordered_set进行去重，最后直接把容器返回即可。

解法二：双指针
这里双指针和上一道题的双指针类似，还是需要固定一个数，这道题我们不用unordered_set进行去重，因为在算法题中可以用，但是在面试题中用unordered_set很可能会挂掉，所以我们海狮正常的用算法进行去重，首先我们海狮先排序，排序可以把相同的元素排在一起，排完序之后先固定一个数，我们先固定首元素，然后对首元素后面的数进行遍历，这里遍历只需要取首尾元素，这道题三数之和我们就转化为了两数之和，我们只需要求后面区间的数中存在两个数加起来等于前面这个数的相反数的组合即可，如果存在，则将其入到vector中，如果不存在则继续遍历，将固定的那个数往后移动，这里我们需要注意的细节是：我们后面的数加起来有三种情况：
第一种：大于前面的数，如果大于前面的数，可以直接将最大数–，因为这个数组被我们排成有序的了，所以不可能用left++，left++只会更大，所以应该是right–。
第二种情况：left+right=-a，这个情况直接入到数组中。
第三种情况：；left+right<-a，如果小于这个数，left++，如果right–只会更小。

接下来我们来谈谈去重的操作：

代码展示：

class Solution 
{
public:
vector<vector<int>> v;
vector<vector<int>> threeSum(vector<int>& nums)
{
    sort(nums.begin(), nums.end());
    int i = 0;
    while (i <= nums.size() - 2)
    {
        int left = i + 1;
        int right = nums.size() - 1;
        while (left < right)
        {
            vector<int> ret;
            int ret1 = nums[left];
            int ret2 = nums[right];
            if (nums[left] + nums[right] == -nums[i])
            {
                ret.push_back(nums[left]);
                ret.push_back(nums[right]);
                ret.push_back(nums[i]);
                v.push_back(ret);
            }
            if (nums[left] + nums[right] < -nums[i])
            {
                while (nums[left] == ret1)
                {
                    left++;
                    if (left >= right)
                    {
                        break;
                    }
                }
            }
            else
            {
                while (nums[right] == ret2)
                {
                    right--;
                    if (left >= right)
                    {
                        break;
                    }
                }
            }
        }
        int j = nums[i];
        while (nums[i] == j)
        {
            i++;
            if (i > nums.size() - 1)
            {
                break;
            }
        }
    }
    return v;
}  
};

7.四数之和

题目：

输出样例和输入样例：

四数之和可以参照三数之和，题目也是类似，我们需要找到四个数的和等于目标的target，但是这四个数的位置不能是一样的，

解法一：暴力解法
暴力解法很简单，只需要用四层循环把每种情况进行遍历一遍即可，最后再用容器进行去重操作。

解法二：双指针
这里和三数取和类似，我们只需要固定第一个数，对后面的数进行三数求和，然后将第一个固定的数逐渐往后遍历即可。

代码展示：

class Solution 
{
public:
    vector<vector<int>> v;
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        vector<vector<int>> ret;
        //排序
        int n=nums.size();
        sort(nums.begin(),nums.end());
        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)
                {
                    int sum=nums[left]+nums[right];
                    if(sum<aim)left++;
                    else if(sum>aim)right--;
                    else
                    {
                        ret.push_back({nums[left++],nums[right--],nums[i],nums[j]});
                        //nums和nums的去重
                        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;
    }
};