【算法】双指针的应用

文章目录

前言
1. 移动零（easy）
2. 复写零（easy）
3. 快乐数（medium）
4. 盛水最多的容器（medium）
5. 有效三角形的个数（medium）
6.和为 s 的两个数字（easy）
7. 三数之和（medium）
8. 四数之和（medium）

前言

常见的双指针有两种形式，⼀种是对撞指针，⼀种是快慢指针。

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

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

快慢指针： 又称为龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。

这种方法对于处理环形链表或数组非常有用。
其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。

快慢指针的实现方式有很多种，最常用的⼀种就是：

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

1. 移动零（easy）

「数组分两块」是非常常见的⼀种题型，主要就是根据⼀种划分方式，将数组的内容分成左右两部分。这种类型的题，⼀般就是使用「双指针」来解决。
1. 题目链接： 283.移动零
2. 题目描述：
给定⼀个数组nums ，编写⼀个函数将所有0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意，必须在不复制数组的情况下原地对数组进行操作。
示例1:
输入：nums = [0,1,0,3,12]
输出：[1,3,12,0,0]
示例2:
输入：nums = [0]
输出：[0]
3. 解法：
在本题中，我们可以用⼀个cur 指针来扫描整个数组，另⼀个dest 指针用来记录非零数序列的最后⼀个位置。根据cur 在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。在cur 遍历期间，使[0, dest] 的元素全部都是非零元素， [dest + 1, cur - 1]的元素全是零。
算法流程：

初始化cur = 0 （用来遍历数组），dest = -1 （指向非零元素序列的最后⼀个位置。因为刚开始我们不知道最后⼀个非零元素在什么位置，因此初始化为 - 1 ）
cur 依次往后遍历每个元素，遍历到的元素会有下面两种情况：
1. 遇到的元素是0， cur 直接 ++ 。因为我们的目标是让[dest + 1, cur - 1] 内的元素全都是零，因此当cur 遇到0 的时候，直接 ++ ，就可以让0 在cur - 1的位置上，从而控制0在[dest + 1, cur - 1] 内；
2. 遇到的元素不是0，dest++，并且交换cur位置和dest位置的元素，之后让cur++ ，扫描下⼀个元素。
  - 因为dest指向的位置是非零元素区间的最后⼀个位置，如果扫描到⼀个新的非零元素，那么它的位置应该在dest + 1的位置上，因此dest先自增 1 ；
  - dest++之后，指向的元素就是0元素（因为非零元素区间末尾的后⼀个元素就是0），因此可以交换到cur所处的位置上，实现[0, dest] 的元素全部都是非零元素，[dest + 1, cur - 1]的元素全是零。

C++代码实现：

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]);                    
        }
    }
};

2. 复写零（easy）

1.题目链接：1089.复写零
2. 题目描述：
给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注意：请不要在超过该数组长度的位置写入元素。请对输入的数组就地进行上述修改，不要从函数返回任何东西。
示例 1：
输入：arr = [1, 0, 2, 3, 0, 4, 5, 0]
输出：[1, 0, 0, 2, 3, 0, 0, 4]
解释：调用函数后，输入的数组将被修改为：[1, 0, 0, 2, 3, 0, 0, 4]
3.解法（原地复写 - 双指针）：
算法思路：
如果「从前向后」进⾏原地复写操作的话，由于 0 的出现会复写两次，导致没有复写的数「被覆盖掉」。因此我们选择「从后往前」的复写策略。
但是「从后向前」复写的时候，我们需要找到「最后⼀个复写的数」，因此我们的⼤体流程分两步：

先找到最后⼀个复写的数；
然后从后向前进⾏复写操作。

算法流程：
a. 初始化两个指针cur = 0，dest = -1（预防开头第一个数就是0）；
b. 找到最后⼀个复写的数：

当dest = 0 ；cur < n 的时候，⼀直执行下面循环：

判断cur位置的元素:
如果是0的话，dest 往后移动两位；
否则，dest 往后移动⼀位。

判断dest时候已经到结束位置，如果结束就终止循环；
如果没有结束，cur++ ，继续判断。

c. 判断dest 是否越界到n的位置：

请添加图片描述

请添加图片描述
C++代码实现：

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
       int cur = 0, dest = -1, num = arr.size();
       // 找到最后一个复写的数
       while(cur < arr.size())
       {
            if(arr[cur]) ++dest;
            else dest += 2;
            if(dest >= num - 1)
                break;
            ++cur;
       }
       // 处理边界情况,如果dest==num说明最后一个复写的数是0
       if(dest == num)
       {
            --cur;
            arr[--dest] = 0;
            --dest;
       }
       // 从后往前完成复写操作
       while(cur >= 0)
       {
            if(arr[cur])
                arr[dest--] = arr[cur--];
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
       }
    }
};

3. 快乐数（medium）

1. 题目链接：202.快乐数
2. 题目描述：
编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。

示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：
输入：n = 2
输出：false
解释：（这里省去计算过程，只列出转换后的数）
2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16
往后就不必再计算了，因为出现了重复的数字，最后结果肯定不会是 1

3. 题目分析:
为了方便叙述，将「对于⼀个正整数，每⼀次将该数替换为它每个位置上的数字的平方和」这⼀个操作记为 x 操作；
题目告诉我们，当我们不断重复 x 操作的时候，计算⼀定会「死循环」，死的方式有两种：

情况⼀：⼀直在 1 中死循环，即 1 -> 1 -> 1 -> 1......
情况⼆：在历史的数据中死循环，但始终变不到 1

由于上述两种情况只会出现⼀种，因此，只要我们能确定循环是在「情况一」中进行，还是在「情况二」中进行，就能得到结果。
简单证明：
a.经过⼀次变化之后的最大值 9 ^ 2 * 10 = 810 (2 ^ 31 - 1) = 2147483647。选⼀个更大的最大9999999999，也就是变化的区间在[1, 810] 之间；
b.⼀个数变化 811 次之后，必然会形成⼀个循环；
c. 因此，变化的过程最终会走到⼀个圈里面，因此可以用「快慢指针」来解决。

4.解法（快慢指针）：
算法思路：
根据上述的题目分析，我们可以知道，当重复执行 x 的时候，数据会陷入到⼀个「循环」之中。而「快慢指针」有⼀个特性，就是在一个圆圈中，快指针总是会追上慢指针的，也就是说他们总会相遇在⼀个位置上。如果相遇位置的值是 1，那么这个数⼀定是快乐数；如果相遇位置不是 1的话，那么就不是快乐数。
C++代码实现：

class Solution {
public:
    int  Square_sum(int num) // 写一个求各位数的平方和
    {
        int sum = 0;
        while(num)
        {
            int tmp = num % 10;
            sum += tmp * tmp;
            num /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        int slow = Square_sum(n); // 指向第一个数
        int fast = Square_sum(slow); // 指向第二个数

        while(slow != fast)
        {
            slow = Square_sum(slow);
            fast = Square_sum(Square_sum(fast));
        }
        return slow == 1;
    }
};

4. 盛水最多的容器（medium）

1. 题目链接：11.盛最多水的容器
2. 题目描述：
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是(i, 0) 和(i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例一：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
在这里插入图片描述
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

3.解法（对撞指针）
设两个指针left ，right 分别指向容器的左右两个端点，此时容器的容积 :
v = (right - left) * min(height[right], height[left])
容器的左边界为 height[left] ，右边界为 height[right]。
为了方便叙述，我们假设「左边边界」小于「右边边界」。
如果此时我们固定⼀个边界，改变另一个边界，水的容积会有如下变化形式：

容器的宽度⼀定变小。
由于左边界较小，决定了水的高度。如果改变左边界，新的水面高度不确定，但是一定不会超过右边的柱子高度（如果比右边柱子高，那么水的高度就是右边的柱子的高度），因此容器的容积可能会增大。
如果改变右边界，无论右边界移动到哪里，新的水面的高度一定不会超过左边界，也就是不会超过现在的水面高度，但是由于容器的宽度小，因此容器的容积⼀定会变小的。

由此可见，左边界和其余边界的组合情况都可以舍去。所以我们可以 left++ 跳过这个边界，继续去判断下⼀个左右边界。

当我们不断重复上述过程，每次都可以舍去大量不必要的枚举过程，直到 left 与 right 相遇。期间产生的所有的容积里面的最大值，就是最终答案。

C++代码实现：

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

5. 有效三角形的个数（medium）

1. 题目链接：611.有效三角形的个数
2. 题目描述：
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
示例 1:
输入: nums = [2, 2, 3, 4]
输出 : 3
解释 : 有效的组合是 :
2, 3, 4 (使用第一个 2)
2, 3, 4 (使用第二个 2)
2, 2, 3

示例 2 :
输入 : nums = [4, 2, 3, 4]
输出 : 4

3. 解法（排序 + 对撞指针）：
我们知道判断是否能构成三角形的条件是：任意两边之和大于第三遍。
但是实际上只需让较小的两条边之和大于第三边即可。
算法思路：
先将数组排序。
我们可以固定⼀个「最长边」，然后在比这条边小的有序数组中找出⼀个二元组，使这个二元组之和大于这个最长边。
设最长边枚举到 i 位置，区间[left, right] 是 i 位置左边的区间（也就是比它小的区间）：

如果 nums[left] + nums[right] > nums[i] ：
- 说明[left, right - 1] 区间上的所有元素均可以与 nums[right] 构成比nums[i] 大的二元组
- 满足条件的有 right - left 种
- 此时 right 位置的元素的所有情况相当于全部考虑完毕， right-- ，进入下⼀轮判断
如果 nums[left] + nums[right] <= nums[i] ：
- 说明 left 位置的元素是不可能与 [left + 1, right] 位置上的元素构成满足条件的二元组
- left 位置的元素可以舍去， left++ 进入下轮循环

C++代码实现

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

6.和为 s 的两个数字（easy）

题目链接：LCR 179. 查找总价格为目标值的两个商品
题目描述：
购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是target。若存在多种情况，返回任一结果即可。

示例 1：
输入：price = [3, 9, 12, 15], target = 18
输出：[3,15] 或者 [15,3]（返回一组即可）
解法（对撞指针）：
因为本题是升序的数组，所以可以使用对撞指针来进行解答

算法思路：

初始化 left ，right 分别指向数组的左右两端（这里不是我们理解的指针，而是数组的下标）
当 left < right 的时候，一直循环

当 nums[left] + nums[right] == target 时，说明找到结果，记录结果，并且返回；
当 nums[left] + nums[right] < target 时：
- 对于 nums[left] 而言，此时 nums[right] 相当于是 nums[left] 能碰到的最大值（这里是升序数组）。如果此时不符合要求，说明在这个数组里面，没有别的数符合 nums[left] 的要求了。因此，我们可以大胆舍去这个数，让 left++ ，去比较下一组数据；
- 那对于 nums[right] 而言，由于此时两数之和是小于目标值的， nums[right]还可以选择比 nums[left] 大的值继续努力达到目标值，因此 right 指针我们按兵不动；
当 nums[left] + nums[right] > target 时，同理我们可以舍去nums[right] ）。让 right-- ，继续比较下一组数据，而left 指针不变（因为他还是可以去匹配比 nums[right] 更小的数的）。

C++代码实现：

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int left = 0, right = price.size() - 1;
        while(left < right)
        {
            if(price[left] + price[right] > target)
                --right;
            else if(price[left] + price[right] < target)
                ++left;
            else
                return {price[left], price[right]};
        }
        // 防止编译器报"不是所有路径都有返回值"的错
        return {};
    }
};

7. 三数之和（medium）

1. 题目链接：15.三数之和
2. 题目描述：
给你一个整数数组 nums ，判断是否存在三元组[nums[i], nums[j], nums[k]]满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是[-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

3. 解法（排序 + 双指针）
与两数之和稍微不同的是，题目中要求找到所有「不重复」的三元组。那我们可以利用在两数之和那里用的双指针思想，来对我们的暴力枚举做优化：

先排序
然后固定⼀个数 a
在这个数后面的区间内，使用「双指针算法」快速找到两个数之和等于 -a 即可。

但是要注意的是，这道题里面需要有「去重」操作⭐️

找到一个结果之后， left 和 right 指针要「跳过重复」的元素；
找到⼀个结果之后， left 和 right 指针要「跳过重复」的元素；

C++代码实现：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // 排序
        vector<vector<int>> ret;
        int n = nums.size();
        for(int i = 0;i <= n - 3;)
        {
            if(nums[i] > 0) // 后面没有相加等于一个负数的数了
                break;
            int left = i + 1, right = n - 1, target = -nums[i];
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum > target)
                    --right;
                else if(sum < target)
                    ++left;
                else
                {
                    // 将满足条件的三个数存入到ret中
                    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;
                }
            }
            // 去重我们开始固定的数a(这里也要注意控制边界)
            ++i;
            while(i <= n - 3 && nums[i] == nums[i - 1])
                ++i;
        }
        return ret;
    }
};

8. 四数之和（medium）

1. 题目链接：18. 四数之和
2. 题目描述：
给你一个由 n 个整数组成的数组nums ，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案。

示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

3. 解法（排序 + 双指针）
算法思路：
a.依次固定⼀个数 a ；
b.在这个数 a 的后面区间上，利用「三数之和」找到三个数，使这三个数的和等于 target - a 即可。

这题几个很恶心的测试案例，会溢出int的范围，所以我们可以使用long long来声明一些变量，具体操作如下：

C++代码实现

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> vv;
        int n = nums.size();
        if(nums[0] > 0 && target < 0)
            return vv;
        if(nums[n - 1] < 0 && target > 0)
            return vv;
        for(int i = 0;i <= n - 4;)
        {
            for(int j = i + 1;j <= n - 3;)
            {
                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) --right;
                    else if(sum < aim) ++left;
                    else
                    {
                        vv.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 - 3 && nums[j] == nums[j - 1]);
                        ++j;
                }
                // 去重三
                ++i;
                while(i <= n - 4 && nums[i] == nums[i - 1]);
                    ++i;
            }
        }
        return vv;
    }
};