双指针算法篇——一快一慢须臾之间解决问题的飘逸与灵动（1）

一. 双指针的含义与形式

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

1.1 对撞指针

一般用于循环结构中，也称为左右指针。

对撞指针从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼

近。

对撞指针的终⽌条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循

环），也就是：

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

1.2 快慢指针

⼜称为⻳兔赛跑算法，其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列

结构上移动。

注意：这种⽅法对于处理环形链表或数组⾮常有⽤。

其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使⽤快慢指针的思想。

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

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

二. 相关题目及讲解

2.1 移动零

「数组分两块」是⾮常常⻅的⼀种题型，主要就是根据⼀种划分⽅式，将数组的内容分成左右两部

分。这种类型的题，⼀般就是使⽤「双指针」来解决。

题目链接：. - 力扣（LeetCode）

题目分析：

1. 首先需要对数组进行原地操作，且不能复制数组，因此放弃开辟新数组进行遍历拷贝的思路

2. 分析题目可知，该函数对数组内的元素进行了分割，分割后一段区间内是原先数组内不为0的元素，另一段则全为0

思路讲解：

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

算法流程：

初始化 cur = 0 （⽤来遍历数组）， dest = -1 （指向⾮零元素序列的最后⼀个位置。

因为刚开始我们不知道最后⼀个⾮零元素在什么位置，因此初始化为 -1 ）。

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) {
        int cur=0;
        int des=-1;
        for(cur=0,des=-1;cur<nums.size();cur++)
        {
            if(nums[cur])
            {
                swap(nums[++des],nums[cur]);
            }
        }

    }
};

2.2 复写零

题目链接：1089. 复写零 - 力扣（LeetCode）

题目分析：

1.原数组自身需要被修改，即调用函数后数组自身元素已经发生变化

2.在复写一次0之后，遍历顺序仍然为之前数组元素的相对顺序，直到数组长度与之前相同为止

思路讲解：

1. 如果我们从前往后遍历并直接原地修改，会导致0之后的元素被覆盖，从而无法完整遍历 2. 复写0的次数就相当于调用函数之后数组与原数组对比所缺少的元素 3. 因此我们先找到原数组遍历的终点，再对其进行复写0的操作，所得数组即为修改后的数组 注意：此时的复写需要从后往前进行！！！

算法流程：

a. 初始化两个指针 cur = 0 ， dest = 0 ；

b. 找到最后⼀个复写的数：

i. 当 cur < n 的时候，⼀直执⾏下⾯循环：

• 判断 cur 位置的元素:

如果是 0 的话， dest 往后移动两位；

否则， dest 往后移动⼀位。

判断 dest 时候已经到结束位置，如果结束就终⽌循环；

如果没有结束， cur++ ，继续判断。

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

i. 如果越界，执⾏下⾯三步：

1. n - 1 位置的值修改成 0 ；

2. cur 向移动⼀步；

3. dest 向前移动两步。

d. 从 cur 位置开始往前遍历原数组，依次还原出复写后的结果数组：

i. 判断 cur 位置的值：

1. 如果是 0 ： dest 以及 dest - 1 位置修改成 0 ， dest -= 2 ；

2. 如果⾮零： dest 位置修改成 0 ， dest -= 1 ；

ii. cur-- ，复写下⼀个位置。

代码实现：

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur=0;
        int dst=-1;
        int n=arr.size();
        while(cur<n)
        {
            if(arr[cur]!=0)
            {
                dst++;
            }
            else
            dst=dst+2;
            if(dst>=n-1)
            {
                break;
            }
            cur++;
        }//找到最后一个复写的数字
        if(dst==n)
        {
            arr[n-1]=0;
            dst=dst-2;
            cur--;
        }//处理边界情况

        while(cur>=0)
        {
            if(arr[cur])
            {
                arr[dst--]=arr[cur--];
            }
            else
            {
                arr[dst--]=0;
                arr[dst--]=0;
                cur--;
            }
        }//从后往前复写
        


    }
};

注意：该题思路不算复杂，但容易忽略边界情况和如何正确处理，建议在理解思路后先尝试 独立完成检验考虑是否完善。

2.3 快乐数

题目链接：202. 快乐数 - 力扣（LeetCode）

题目分析：

1. 题中明确指出，如此操作之后只会有两种结果，一种是无限循环却始终到不了1，另一种是变为1成为快乐数

2. 我们需要明白，所谓的无限循环，实际上是一种一系列数字组成的环，而非是无数不同的数导致的循环。

简单证明： a. 经过⼀次变化之后的最⼤值 9^2 * 10 = 810 ( 2^31-1=2147483647 。选⼀个更⼤的最 ⼤ 9999999999 )，也就是变化的区间在 [1, 810] 之间； b. 根据「鸽巢原理」，⼀个数变化 811 次之后，必然会形成⼀个循环； c. 因此，变化的过程最终会⾛到⼀个圈⾥⾯，因此可以⽤「快慢指针」来解决。

思路讲解：

1. 我们初始化两个变量slow和fast，分别记录当前的值和下一次经过平方变化后的值

2. 利用快慢指针的特性来判断是否会成环导致循环

3. 如果判断过程中slow等于1，则可以直接输出

代码实现：

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

    }
};

小结：本文主要介绍了双指针算法的思路与应用，并结合相关题目进行分析和讲解。希望可以对各位的学习产生帮助，欢迎各位佬前来支持斧正！！！