双指针算法实战：移动零、快乐数与盛水容器解析

1. 双指针的介绍

双指针算法是一种常用的算法技巧，通常用于解决数组或链表相关的题目。双指针算法的核心思想是使用两个指针在数组或链表上移动，这里的指针并不是只是指指针，我们可以用数组下标来代替，以达到解决问题的目的。根据具体问题，双指针可以分为以下几种类型：

1. 左右指针（对撞指针）

左右指针通常用于处理数组中的问题，其中一个指针从数组的开始位置向后移动，另一个指针从数组的结束位置向前移动。

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

left == right （两个指针指向同一个位置）left > right （两个指针错开）

典型问题：

• 二分查找：在有序数组中查找一个特定的元素。
• 两数之和：在数组中找到两个数，使它们的和等于一个给定的数。

2. 快慢指针

快慢指针主要用于处理链表中的问题，两个指针从同一位置出发，一个指针（快指针）每次移动两个节点，另一个指针（慢指针）每次移动一个节点。

典型问题：

• 判断链表中是否有环：Floyd 判圈算法（龟兔赛跑算法）。
• 找到链表的中间节点：快指针到达终点时，慢指针正好在中间。

双指针算法的关键在于指针的移动策略和终点的判断条件，根据具体问题，双指针的移动策略和判断条件可能会有所不同。

2. 题目练习讲解

2.1 移动零

283. 移动零 - 力扣（LeetCode）

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]

示例 2:

输入: nums = [0] 输出: [0]

算法思路

在本题中，我们可以用一个 cur 指针来扫描整个数组，另一个 dest 指针用来记录非零数序列的最后一个位置。根据 cur 在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。在 cur 遍历期间，使 [0, dest] 的元素全部都是非零元素， [dest + 1, cur - 1] 的元素全是零。[cur,n-1] 是待处理的元素。

首先，我们让 dest 指向 -1 的位置，cur 指向数组的首元素，通过循环控制 cur 的移动，无论 cur 指向谁，一次循环过后都要 ++，而当 cur 指向的数据是非 0 元素时，我们就让 dest++, 让加之后的 dest 与 cur 进行元素交换。详细就是：

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

代码展示

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for(int cur = 0, dest = -1; cur < nums.size(); cur++)
            if(nums[cur]) // 处理非零元素
                swap(nums[++dest], nums[cur]);
    }
};

当然，我们也可以让 dest 指向首元素，后续算法逻辑类似，只是变成了先交换在++。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for(int cur = 0, dest = 0; cur < nums.size(); cur++)
            if(nums[cur]) // 处理非零元素
                swap(nums[dest++], nums[cur]);
    }
};

2.2 复写零

1089. 复写零 - 力扣（LeetCode）

算法思路

同样这道题我们用双指针的算法，我们首先普遍会想到定义两个指针，从前向后开始复写，从首元素开始移动，在移动过程中由于 0 会写两次，我们会发现后一个数据会被覆盖就会达不到效果。

故当我们换成从后向前复写时，可以避免这种情况，但是我们需要找到复写的最后一个元素。

我们还是定义两个指针：

初始化两个指针 cur = 0，dest = -1； b. 找到最后一个复写的数： i. 当 cur < n 的时候，一直执行下面循环： • 判断 cur 位置的元素: ◦ 如果是 0 的话，dest 往后移动两位； ◦ 否则，dest 往后移动一位。 • 判断 dest 时候已经到结束位置，如果结束就终止循环； • 如果没有结束，cur++，继续判断。 从 cur 位置开始往前遍历原数组，依次还原出复写后的结果数组： i. 判断 cur 位置的值：

1. 如果是 0：dest 以及 dest - 1 位置修改成 0，dest -= 2；
2. 如果非零：dest 位置修改成 0，dest -= 1； ii. cur--，复写下一个位置。

while(cur>=0){ 
    if(arr[cur]) arr[dest--]=arr[cur--]; 
    else{ 
        arr[dest--]=0; 
        arr[dest--]=0; 
        cur--; 
    } 
}

我们发现有些情况会数组越界，超出一位，当我们往前遍历复写的时候就会出现问题，因为数组外赋值了。

所以要处理数组越界的情况

如果越界，n - 1 位置的值修改成 0；cur 向移动一步；dest 向前移动两步。

代码展示

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

2.3 快乐数

202. 快乐数 - 力扣（LeetCode）

算法思路

首先可以将题目解答猜成两部分，第一部分是求取每个位数上的平方和，第二步就是与 1 进行比较。

通过快乐数的定义我们发现其实当它结果为 1 时，也会陷入一个 1 的循环。所以不管那种过程，累加次都会陷入循环，最终都会走到一个环中进行循环。

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

简单证明一下：

经过一次变化之后的最大值 9^2 * 10 = 810 ( 2^31-1=2147483647 。选一个更大的最大 9999999999 )，也就是变化的区间在 [1, 810] 之间；根据「鸽巢原理」，一个数变化 811 次之后，必然会形成一个循环；因此，变化的过程最终会走到一个圈里面，因此可以用「快慢指针」来解决将「对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和」这一个操作记为 x 操作根据上述分析，我们可以知道，当重复执行 x 的时候，数据会陷入到一个「循环」之中。而「快慢指针」有一个特性，就是在一个圆圈中，快指针总是会追上慢指针的，也就是说他们总会相遇在一个位置上。如果相遇位置的值是 1，那么这个数一定是快乐数；如果相遇位置不是 1 的话，那么就不是快乐数。

代码展示

class Solution {
public:
    int ret(int n){
        int sum=0;
        while(n){
            int a=n%10;
            sum+=a*a;
            n=n/10;
        }
        return sum;
    }
    bool isHappy(int n) {
        int slow=n;
        int fast=ret(n);
        while(slow!=fast){
            slow=ret(slow);
            fast=ret(ret(fast));
        }
        return slow==1;
    }
};

2.4 盛最多水的容器

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

这道题我们首先会想到枚举，通过暴力的解法将每一种的体积算出来，选出最大的。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n=height.size();
        int ret=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                ret = max(ret, min(height[i], height[j]) * (j - i));
            }
        }
        return ret;
    }
};

但是这种解法会超时。所以需要换一种思路。我们可以采用对撞指针的思路。

算法思路

设两个指针 left，right 分别指向容器的左右两个端点，此时容器的容积 :v = (right - left) * min( height[right], height[left] ) 容器的左边界为 height[left]，右边界为 height[right]。我们假设「左边边界」小于「右边边界」。如果此时我们固定一个边界，改变另一个边界，水的容积会有如下变化形式：容器的宽度一定变小。

由于左边界较小，决定了水的高度。如果改变左边界，新的水面高度度不确定，但是一定不会超过右边的柱子高度，因此容器的容积可能会增大。

• 如果改变右边界，无论右边界移动到哪里，新的水面的高度一定不会超过左边界，也就是不会超过现在的水面高度，但是由于容器的宽度减小，因此容器的容器一定会变小的。

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

代码展示

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