【C++】优选算法必修篇之双指针实战：移动零 & 复写零

我不是呆头

发布于 2025-12-20 14:19:15

2800

文章被收录于专栏：学习学习

应用场景

在算法中，双指针（Two Pointers） 是一种极具代表性的高效技巧。它通过维护两个索引或指针，在一次遍历中完成双层循环才能解决的问题，从而显著降低时间复杂度。常见的双指针形态主要分为两类：对撞指针和快慢指针。这两种形式几乎覆盖了所有数组、字符串与链表中的高频算法场景，是算法思维中必须掌握的核心技巧。

对撞指针（Collision Pointers）:

对撞指针一般用于有序数组或字符串等结构中，其特征是两个指针分别从两端开始，向中间移动。通过左右相向的方式逐步缩小搜索范围，从而在一次扫描中解决问题。
这种方法常用于判断字符串是否为回文、有序数组的两数之和、区间反转、移动零或划分问题等。它的本质思想是——利用数据的有序性或对称性，通过条件判断决定哪一侧的指针移动，最终达到在 O(n) 时间内完成目标的效果。
对撞指针的优点是逻辑直观、空间占用低，通常仅需常数级的额外空间即可完成操作。

快慢指针（Fast-Slow Pointers）:

快慢指针常用于链表或数组的遍历、修改与结构判断中。两者方向一致，但移动速度不同：快指针一般一次移动两步或多步，而慢指针一次移动一步。通过速度差，快指针可以“探测”结构特征或帮助慢指针完成就地操作。
这种方法常见于链表判环、寻找中点、删除重复元素、原地压缩数组、复写 0 等问题。
其核心思想是让快指针负责探索与筛选，慢指针负责记录与写入。这样能在单次遍历中实现去重、压缩、复制等效果，无需额外数组或中间存储，既高效又节省空间。

1. 移动零

1.1 题目链接

链接直达请点击<----------

1.2 题目描述

1.3 题目示例

1.4 题目思路

我们可以用一个快排思想：用一个right指针（快指针）用来遍历整个数组，另外一个left指针（慢指针）用来记录下一个非零元素应该存放的位置。
当right指针扫描到非零元素时，就先将left++，因为开始指向的位置在-1处，然后将其移动到left指针所指的位置。这样可以确保所有非零元素按照原有顺序被前移。right指针继续向后遍历，直到扫描完整个数组。
在right指针遍历结束后，left指针之前的部分已经全部是非零元素，left指针及其之后的位置则应当全部填充为 0。
在这期间，0 ~ left期间元素都将是非0；left+1 ~ right-1期间的元素都是0

1.5 核心代码实现

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int left = -1;
        int right = 0;
        for (right = 0; right < nums.size(); right++)
        {
            if (nums[right] != 0)
                swap(nums[right], nums[++left]);
        }
    }
};

1.6 示例测试（总代码）

//零移动和复写零

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int left = -1;
        int right = 0;
        for (right = 0; right < nums.size(); right++)
        {
            if (nums[right] != 0)
                swap(nums[right], nums[++left]);
        }
    }
};

int main()
{
    vector<int> nums = { 0,1,0,3,2 };
    Solution().moveZeroes(nums);
    for (auto e : nums)
    {
        cout << e << " ";
    }
    cout << endl;

    return 0;
}

2. 复写零

2.1 题目链接

链接直达请点击<----------

2.2 题目描述

2.3 题目示例

2.4 题目思路

当我们从前往后复写的时候，每当我们遇到一个 0 时，需要在它后面再插入一个 0，然后原数组后续元素整体右移。但由于数组长度是固定的，超出边界的部分要被自动舍弃。所以核心难点在于如何在不破坏未处理数据的情况下完成移动。

当我们正着复写下面这个数组的时候：
arr = [1, 0, 0, 2, 3]

我们在处理第一个 0 时，就提前右移覆盖掉了第二个 0；第二个 0 还没来得及被复写，它就被前一步操作的结果顶掉了；最终结果变成了错误的：

[1, 0, 0, 0, 2]

实际正确结果应是：

[1, 0, 0, 0, 0]

我们可以借助快慢指针（Fast-Slow Pointers） 的思想来实现。

首先，通过一次遍历，计算“如果每个 0 都被复写一次，整个数组理论上需要多长”。这个虚拟长度（用快指针 fast 表示）会超过数组的实际长度，而慢指针 slow 则用来记录当前正在处理的元素位置。遍历过程中，fast 会根据元素是否为 0 来累加长度：若元素不是 0，长度加 1；若是 0，则长度加 2。这样，当 fast 的值刚好达到或超过数组长度时，就说明慢指针的位置到达了数组中最后一个需要处理的元素。
接下来进入第二阶段，也就是倒序写入阶段。此时我们从 slow 和 fast 两个指针的末端开始，从右向左遍历。这样做的好处是可以避免在复写 0 时覆盖掉尚未处理的元素。如果当前元素（slow指向的元素）是非零，则直接将其写入当前位置（fast指向的位置）；若是 0，则需要写入两次（一个当前位置、一个前一位置），并且注意边界防止越界写入。通过这种倒序的处理方式，我们能在不额外开辟空间的情况下完成所有复写操作。

如图：我们通过这段示例可以知道找到在复写中最后一个需要处理的元素是4

 int slow = 0; 
 int fast = -1; 
 int n = arr.size();
 //找最后一个数
 while (slow < n)
 {
     if (arr[slow]) fast++;
     else          fast += 2;

     if (fast >= n - 1) break;
     else               slow++;
 }

接下来我们进行第二步，从右向左遍历进行复写

当出现 fast == n 时，说明最后一次复写操作正好溢出了数组长度。例如数组 [1,0,2,3,0,4]，长度为 5，最后一个元素是 0。复写这个 0 需要写入两个 0（一个是原来的，一个是复写的），但第二个 0 会落在下标 5 上，也就是数组边界之外。这时我们只能在数组的最后一个合法位置（下标 n−1）写入一个 0，然后将其余逻辑稍作调整。

        //处理边界情况
        if (fast == n)
        {
            arr[n - 1] = 0;
            slow--;
            fast -= 2;
        }

于是代码执行 arr[n - 1] = 0;，在最后一个位置写入一个 0；接着 slow-- 将原数组指针向前移动一位，表示刚才的 0 已经部分处理完成，不再继续参与复写；最后 fast -= 2 是为了让复写指针同步回退两位，确保后续从后往前的填充操作可以正确对应。

//从后向前完成复写操作
while (slow >= 0)
{
    if (arr[slow]) arr[fast--] = arr[slow--];
    else
    {
        arr[fast--] = 0;
        arr[fast--] = 0;
        slow--;
    }
}

2.5 核心代码实现

class Solution2{
public:
    void duplicateZeros(vector<int>& arr)
    {
        int slow = 0; 
        int fast = -1; 
        int n = arr.size();
        //找最后一个数
        while (slow < n)
        {
            if (arr[slow]) fast++;
            else          fast += 2;

            if (fast >= n - 1) break;
            else               slow++;
        }

        //处理边界情况
        if (fast == n)
        {
            arr[n - 1] = 0;
            slow--;
            fast -= 2;
        }

        //从后向前完成复写操作
        while (slow >= 0)
        {
            if (arr[slow]) arr[fast--] = arr[slow--];
            else
            {
                arr[fast--] = 0;
                arr[fast--] = 0;
                slow--;
            }
        }

    }
};

2.6 示例测试（总代码）

//零移动和复写零

#include<iostream>
#include<vector>
using namespace std;

class Solution2{
public:
    void duplicateZeros(vector<int>& arr)
    {
        int slow = 0; 
        int fast = -1; 
        int n = arr.size();
        //找最后一个数
        while (slow < n)
        {
            if (arr[slow]) fast++;
            else          fast += 2;

            if (fast >= n - 1) break;
            else               slow++;
        }

        //处理边界情况
        if (fast == n)
        {
            arr[n - 1] = 0;
            slow--;
            fast -= 2;
        }

        //从后向前完成复写操作
        while (slow >= 0)
        {
            if (arr[slow]) arr[fast--] = arr[slow--];
            else
            {
                arr[fast--] = 0;
                arr[fast--] = 0;
                slow--;
            }
        }

    }
};

int main()
{
    vector<int> nums1 = { 0,1,0,3,2 };
    Solution2().duplicateZeros(nums1);

    for (auto e1 : nums1)
    {
        cout << e1 << " ";
    }
    cout << endl;

    return 0;
}