【C/C++算法】从浅到深学习---双指针算法（图文兼备 + 源码详解）

绪论：冲击蓝桥杯一起加油！！

每日激励：“不设限和自我肯定的心态：I can do all things。 — Stephen Curry”

绪论​：
本章是新开篇章也是算法的第一篇章----双指针算法，双指针算法是算法中非常入门门且基础的，本章将带你了解什么是双指针以及双指针中常见的情况，将主要通过八道题目带你快速的边学边做边认识，逐步深入探究双指针奥秘，接着还会快速更新滑动窗口、二分等算法系列敬请期待。
————————
早关注不迷路，话不多说安全带系好，发车啦（建议电脑观看）。

双指针

常⻅的双指针有两种形式，⼀种是对撞指针，⼀种是左右指针，对撞指针：⼀般⽤于顺序结构中，也称左右指针

对撞指针：⼀般⽤于顺序结构中，也称左右指针。

• 对撞指针从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。
• 对撞指针的终⽌条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循 环），也就是：

1. left == right （两个指针指向同⼀个位置）
2. left > right （两个指针错开）

快慢指针：⼜称为⻳兔赛跑算法，其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。
这种⽅法对于处理环形链表或数组⾮常有⽤。
其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使⽤快 慢指针的思想。 快慢指针的实现⽅式有很多种，最常⽤的⼀种就是：

• 在⼀次循环中，每次让慢的指针向后移动⼀位，⽽快的指针往后移动两位，实现⼀快⼀慢

具体训练：

1. 移动零（数组划分/分块）

题解核心逻辑：

根据数据划分加数据划分非0和0元素的区间，使用双指针dest和cur进行遍历一遍即可，符合条件的放入dest中，不符合的移动到后面。
具体见代码注释：

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        //这题分析：需要将一个数组中的元素的0全部放到最后，而前面就是非0的那么，就有很明显的数组划分感觉
        //那么我们就使用数组划分思想：双指针来处理
        //定义两变量
        int des = -1 ;
        for(int cur = 0; cur < nums.size();cur++){
            //判断条件：是否为0 
            //若不为0（符合条件）：放入到des + 1位置处，并des填加1（可以理解为：让0 ~ des区域添加了一个新元素）：
            if(nums[cur] != 0){
                swap(nums[des+1],nums[cur]);
                des++;
            }
            //如果等于0，则表示不符合条件，那么继续往后
        }
    }
};

拓展：这个地方的双指针算法（数组划分）本质就是快速排序中使用的那个双指针排序方法，只不过快排并不是以0进行划分。

2. 复写零（快慢指针确定位置）

题解核心逻辑：

1. 从左往右在不移动值的情况下进行双指针操作，确定cur和dest的最终的位置
2. 特殊处理一下当dest越界的情况
3. 使用当前的cur和dest进行从右往左的双指针

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur,dest;
        for(cur = 0,dest = -1;cur < arr.size();cur++){
            if(arr[cur] == 0){
                dest++;
            }
            dest++;
            if(dest >= arr.size()-1){
                break;
            }
        }
        
       if(dest == arr.size()){
            arr[arr.size()-1] = 0;
            dest -=2;cur--;
       }

        for(;dest >= 0;cur--,dest--){
            if(arr[cur] == 0){
                arr[dest] = 0;
                dest--;
            }
            arr[dest] = arr[cur];
        }
    }
};

3.快乐数（快慢指针确定是否成环）

题目：

分析题目，解决问题并提出问题：

若是判断的数是快乐数，则直接判断快乐数是比较简单的：将一个数中的位数全都取出来运行，得到下一个数，不断循环判断，只到数为1时退出循环

主要的问题是当一个数，并不是快乐数，则会无限循环，这如何解决？
这题本质就两种情况：

第一种情况较好理解、第二种为什么这样画呢
因为鸽巢原理（抽屉原理）：
对于这种会产生无限的值的情况，并且该值是有范围的情况下，最终一定会出现重复值（有点抽象：理解成n的范围 1 ~ 9：假如同上操作，当不断的循环过程中，一定会将所有情况都发生一遍（最大值就是 9² ，他一定会在1 ~ 9²范围内不断的循环出值），当所有情况都发生后，就一定会出现重复的值）

第二种方法的解决方法：需要你记住下，对于这种出现死循环的情况使用：快慢指针（也是双指针）
快慢指针：
快指针每次移动两步、慢指针每次移动1步
这样当有循环后快慢指针最终在循环内一定是会遇到的
当遇到时就判断值即可，若是1则表示第一种情况，若非1就是第二种情况

这样接解决了无限循环情况：
那么此时我们注意的时，本题的快慢指针，这两个指针指向的其实是数据，而走一步就是执行一步快乐数操作，而走两步是执行两步快乐数操作。

题解核心逻辑：

1. 使用快慢双指针，不断的去遍历
2. 当发生重复时，一定是有循环了，而这个循环的值若不是1则就不是快乐数了！！

class Solution {
public:
//处理快乐数操作
    int handle(int n){
        int res= 0;
        while(n)
        {
            res += (n % 10)*(n % 10);
            n /= 10;
        }
        return res;
    }

    bool isHappy(int n) {
        //1. 不断的循环n只到相遇
        //快慢指针 slow  fast
        int slow = handle(n),fast = handle(handle(n));
        cout << slow << fast;
        //使用一个hash来判断值是否重复过
        unordered_map<int,int> hash;
        while(slow != fast)
        {
            slow = handle(slow);
            fast = handle(handle(fast));
        }
        return slow == 1;
    }
};

4. 盛最多水的容器（分析题目使用对撞双指针快速排除多个情况得到答案）

题目：

分析题目并提出，解决方法：

暴力解法：枚举所有情况，并求出结果，最终取出最大值

假设容器：

当拿出6 ~ 4这两个高度，来当作蓄水的柱子时：

1. 计算出结果后，对于高度值较小的柱子(4)来说，就不用考虑了
2. 因为木桶效应（蓄水由短板控制高度）它已经确定了他的高度的，我们就能将他排除，也就不要去算内部的值了，因为最小高度已经确定，且遍历内部数据宽度一定减小，当遇到比他高的不能提高容积，遇到比他还低的甚至还有降低最小高度导致容积更小，所以就能直接排除较小值，然后继续遍历其他柱子的情况。
3. 具体如下图：
   

题解核心逻辑：

1. 通过上面的分析可以得知，当判断一个区域后，可以直接排除掉较小值
2. 所以遍历整个数组，遍历方法：将高度较小的值逐一排除缩小区域
3. 并算出所有区域的值并且使用max函数，保存最大值
4. 最终所有区域遍历完后就将得出答案

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

5. 有效三角形的个数（单调性对撞双指针）

题目：

分析题目并提出，解决方法：

暴力解法：枚举所有三种情况，并判断是否能组成三角形
优化：

1. 判断三角形：
   1. 两边之和大于第三边即可， 推出：用两个较小的边之和大于第三边就一定是三角形（a + b > c）
2. 利用单调性，使用双指针算法来解决问题
   1. 首先固定最大值
   2. 然后选择较小的两边，并不是随便的选择，而是根据单调性选择可选择范围内的最大和最小两条边，来查看情况
   3. 分析得出：较小边此时只有两种可能：a + b > c / a + b <= c
      1. 若 a + b > c：则表示a ~ b 区间内的所有数都将大于c，因为在不动right的情况下一定left，一个比a大的数 + b 一定大于 c，就能直接快速的知道多个符合条件值，个数为：right - left 然后right就完成工作了再继续遍历，也就是right–即可
      2. 若 a + b <= c：则表示不符合条件，此时移动right是没有意义的因为 a + 一个比b还小的数一定也是不符合条件的所以直接left++即可
   4. 得出较小两个值中所有情况后，移动最大值，继续重复

题解核心逻辑：

1. 先固定最大的数
2. 在最大的数的左区间内，使用双指针算法，快速的统计处符合要求的三元组的个数

具体如下图：

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());//先给数组排序

        //遍历数组，求出所有满足条件的三元组
        //从数组最后一个开始往前遍历，也就固定最大的一边
        int res = 0;
        for(int i = nums.size()-1; i > 1;i--){
            //再从最大边的左边区间，求出所有符合条件的三元组

            //使用双指针算法
            int left = 0,right = i - 1; 
            while(left < right){
                if(nums[left] + nums[right] > nums[i]){
                    //若 a + b > c ，则left ~ right 区间内，固定right移动left的所有三元组都符合
                    //个数为：
                    res += right - left;
                    right--;
                }
                else{
                    left++;
                }
            }
        }
        return res;
    }
};

6. 查找总价格为目标值的两个商品（两数之和，单调双指针）

题目：

分析题目并提出，解决方法：

暴力解法：非常好想也就是两层for循环遍历出所有情况，但时间复杂度可能较高
优化：使用双指针 - 对撞指针

如图：left + right 和 target比较
只有三种情况：

1. left + right > target：right–（left++的话值仍然增加所以只能right–）
2. left + right < target：left++（如上图情况，此时只能left++，因为right–只会更小）
3. left + right == target：找到结果并返回

题解核心逻辑：

1. 使用双指针对撞遍历，遍历一边即可得到结果

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

15. 三数之和（单调性 + 对撞双指针 结合两数之和理解）

题目：

分析题目并提出，解决方法：

分析题目：可知我们需要找到三个不同位置的数，让他们之和最终等于0
暴力解法：排序 + 暴力遍历 + set去重

优化：当我们排完序后，对于有序的数组来说，一定要记得可能使用：二分 / 双指针算法，此处我们使用双指针算法
双指针算法：
此处需要找到的是三数之和等于0，我们可以先固定一个数再使用两数之和的方法找到前面固定数的相反数，这样三数之和就会为0
此处需要注意的是：

1. 和之前的两数之和不同的是，当找到一个结果时，要继续遍历查找出所有结果。
2. 题目还要求要去重，对于这个要求排序有一定程度就是为了解决这个问题，具体操作：当找到一种结果后，left right指针在移动的过程中，要跳过重复元素，同样对于最外层的固定数的指针i也是同样跳过重复的值
3. 其中还要注意越界问题，在跳过重复值的过程中一定要注意

题解核心逻辑：

具体如下图：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //1. 排序
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        //2. 使用双指针遍历，并完成去重

        for(int i = 0 ; i < nums.size()-2 && nums[i] <= 0;i++){
            // -4 -4 1 1 1 0 0 0 2 3 3 5
            int left = i+1,right = nums.size()-1;
            while(left < right)
            {
                int target = -nums[i];
                if(nums[left] + nums[right] > target){
                    right--;
                }else if(nums[left] +nums[right] < target){
                    left++;
                }else{
                    //left + right == target
                    res.push_back({nums[i],nums[left],nums[right]});
                    right--;left++;
                    while(left < right && nums[right] == nums[right+1]){//判断--后的right和之前的是否一致若一致则继续--
                        right--;
                    }
                    // right--;
                    while(left < right && nums[left] == nums[left-1]){//同理判断和前面的是否一致若一致则继续++
                        left++;
                    }
                    // left++;
                }
                // cout << "left:"<< left << "right:" << right <<endl;
            }
            // cout << "i:" << i <<endl;
            //处理：跳过重复的值的方法
            while(i+1 < nums.size()-2 && nums[i] == nums[i+1]){
                i++;
            }
        }
        return res;
    }
};

8. 四数之和（同上）

题目：

分析题目并提出，解决方法：

目的：a + b + c + d = target，并且要去重
在做这题之前您一定要先理解三数之和和两数之和，在他们的基础上修改：
三数之和：目的是：a + b + c = 0，而此时他是需要 a + b + c + d = target
三数之和变成了：a + b + c = target - d
再推导出两数之和需要的目标就是：c + d = target - a - b

所以和三数之和类似使用排序 + 双指针
固定a，b，在使用双指针
其中同样的还要注意去重

题解核心逻辑：

具体如下图：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //1. 排序
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        //2. 使用双指针遍历，并完成去重

        for(int i = 0 ; i < nums.size()-2 && nums[i] <= 0;i++){
            // -4 -4 1 1 1 0 0 0 2 3 3 5
            int left = i+1,right = nums.size()-1;
            while(left < right)
            {
                int target = -nums[i];
                if(nums[left] + nums[right] > target){
                    right--;
                }else if(nums[left] +nums[right] < target){
                    left++;
                }else{
                    //left + right == target
                    res.push_back({nums[i],nums[left],nums[right]});
                    right--;left++;
                    while(left < right && nums[right] == nums[right+1]){//判断--后的right和之前的是否一致若一致则继续--
                        right--;
                    }
                    // right--;
                    while(left < right && nums[left] == nums[left-1]){//同理判断和前面的是否一致若一致则继续++
                        left++;
                    }
                    // left++;
                }
                // cout << "left:"<< left << "right:" << right <<endl;
            }
            // cout << "i:" << i <<endl;
            //处理：跳过重复的值的方法
            while(i+1 < nums.size()-2 && nums[i] == nums[i+1]){
                i++;
            }
        }
        return res;
    }
};

本章完。预知后事如何，暂听下回分解。

如果有任何问题欢迎讨论哈！

如果觉得这篇文章对你有所帮助的话点点赞吧！

持续更新大量算法细致内容，早关注不迷路。

​