【优选算法必刷100题】第001~002题（双指针算法）：移动零、复写零问题

用户11915063

发布于 2025-11-20 09:54:46

310

双指针算法介绍

常见双指针分为两种：

对撞/左右指针
快慢指针

对撞指针：

一般用于顺序结构中，也称左右指针。

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

快慢指针：

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

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

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

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

001.移动零

【数组分块】是非常常见的一种题型，主要就是根据一种划分方式，将数组的内容分成左右两部分。这种类型的题，一般就是使用【双指针】来解决。

题目链接：

283.移动零-力扣（LeetCode）

题目描述：

题目示例：

解法：(快排的思想：数组划分区间-数组分块)

算法思路：

首先定义两个指针cur和dest，这里不是真正意义上的指针，而是用作数组下标， cur 指针来扫描整个数组，另一个 dest 指针用来记录非零的最后一个位置，根据 cur 在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分
区间划分为3个[0,dest]表示非0元素，[dest+1，cur-1]表示0元素，[cur,n-1]表示待处理元素

算法流程：

1.初始化 cur=0（用来遍历数组），dest=-1（指向非零元素序列的最后一个位置。因为刚开始我们不知道最后一个非零元素在什么位置，因此初始化为 -1）

2.cur 依次往后遍历每个元素，遍历到的元素会有下面两种情况：

当cur往后遍历遇到的数字是0的话，cur++即可，因为我们要让[dest+1,cur-1]的位置全部变为0，此时符合我们划分区间的情况，只需要让cur继续往后遍历即可
当cur往后遍历遇到的数字是非0的话，就让cur位置的数字与dest+1位置的数字进行交换，然后cur++，因为我们的目的是将[0,dest]区间变为非0，[dest+1,cur-1]区间变为0，dest表示非0元素的最后一个位置，所以要将遇到的非0元素放到前面而保证非0元素的相对顺序不变，就要将dest+1（第一个0的位置）的位置与cur位置进行交换，此时cur与dest+1的位置交换过后，刚好能满足我们区间划分的要求

C++代码演示：

class Solution 
{
public:
    void moveZeroes(vector<int>& nums) 
    {
        for(int dest=-1,cur=0;cur<nums.size();cur++)
        {
            if(nums[cur])//不等于0
                swap(nums[++dest],nums[cur]);
        }    
    }
};

算法总结&&笔记展示：

这里用到的方法是我们学习【快排算法】的时候，【数据划分】过程的重要一步。如果将快排算法拆解的话，这一小段代码就是实现快排算法的【核心步骤】。

博主笔记（字迹有点丑，请大家见谅）：

002.复写零

题目链接：

1089.复写零-力扣（LeetCode）

题目描述：

题目示例：

解法：（“异地”操作优化为“就地”操作）

算法思路：

如果【从前往后】进行原地复写时，可能会遇到覆盖掉原来要复写的非0数，从而导致原来要复写的数找不到，因此我们选择【从后往前】进行复写
但是我们进行【从后往前】进行复写时，需要找到最后一个复写的数，此时我们的大概思路已经有了：（1）找到最后一个复写的数，（2）【从后往前】进行复写

算法流程：

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

2.找到最后一个复写的数：

判断 cur 位置的元素：（1）如果是 0 的话，dest 往后移动两位；（2）否则，dest 往后移动一位
判断 dest 这时候是否到结束位置，如果结束就跳出循环；
没有结束，cur++，继续判断

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

如果越界，执行下面三步：

n-1（数组最后一位）位置置为0
dest向前移动两位（dest-=2）；
cur向前移动一位（cur--）

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

先判断 cur 位置的值：

如果是 0 ：dest 位置修改为0（arr[dest--]=0）以及 dest-1 （arr[dest--]=0）位置修改成 0 ，dest向前移动两步（dest-=2）；
如果是非0：dest 位置修改成 0 ，dest -= 1；

cur--，复写下一个位置

C++代码演示：

class Solution
{
public:
    void duplicateZeros(vector<int>& arr)
    {
        //1.先找到最后一个复写的数
        int cur = 0, dest = -1, n = arr.size();
        while (cur < n)
        {
            if (arr[cur]) dest++;
            else dest += 2;
            if (dest >= n - 1) break;//dest越界就跳出循环，=是判断当dest走到n的位置特殊情况
            cur++;
        }
        //2.处理边界情况
        if (dest == n)
        {
            arr[n - 1] = 0;
            cur--;
            dest -= 2;
        }
        //从后往前复写
        while (cur >= 0)
        {
            if (arr[cur]) arr[dest--] = arr[cur--];
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
};