双指针算法实战：移动零与复写零详解

双指针算法介绍

双指针是处理数组和链表问题的利器，常见形式主要有两种：对撞指针和快慢指针。

对撞指针

对撞指针通常用于顺序结构，也叫左右指针。两个指针分别从序列的两端向中间移动，一个从左端开始，另一个从右端开始，逐渐逼近。终止条件通常是两指针相遇（left == right）或错开（left > right）。

快慢指针

又称龟兔赛跑算法，核心思想是在序列上以不同速度移动两个指针。这种方法在处理环形链表、检测循环或需要分区时非常有效。最经典的实现是一次循环中，慢指针每次移动一位，快指针每次移动两位。

01. 移动零

这道题的核心在于将非零元素移到前面，同时保持相对顺序。这其实是一种典型的【数组划分】问题，利用双指针可以将数组分为两部分处理。

283. 移动零 - 力扣（LeetCode）

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意，必须在原数组上操作，不能拷贝额外的数组。

算法思路

我们可以用 cur 指针扫描整个数组，用 dest 指针记录非零序列的最后一个位置。目标是让 [0, dest] 区间内全是非零元素，[dest+1, cur-1] 区间内全是零。

具体流程如下：

1. 初始化 cur = 0 用于遍历，dest = -1 指向非零元素区间的末尾。初始化为 -1 是因为刚开始我们不知道第一个非零元素在哪里。
2. 遍历过程中，如果当前元素 nums[cur] 为 0，直接跳过，因为我们的目标就是让这部分区域最终变成 0。
3. 如果 nums[cur] 不为 0，说明找到了一个新的非零元素。此时先将 dest 自增 1，然后交换 nums[dest] 和 nums[cur]。这样就把新发现的非零元素挪到了正确的位置。

这种写法本质上借用了快速排序中'分区'的思想，只是这里只关注非零元素。

C++ 代码演示

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

02. 复写零

这道题要求将数组中的每个 0 都复写一份，被复写的元素向后推移，超出长度的元素则丢弃。难点在于原地操作时，如果从前向后处理，后面的数据会被覆盖，所以我们需要从后向前进行复写。

1089. 复写零 - 力扣（LeetCode）

题目描述

在一个固定的数组中，如果某个元素是 0，则将其复写一次，后续元素依次向右移动。注意数组长度固定，超出的部分截断。

算法思路

由于 0 会占用额外空间导致后续元素位移，直接从前向后修改会覆盖未处理的数据。因此策略分为两步：

1. 确定边界：先找到最后一个需要复写的元素在原数组中的位置。这可以通过模拟过程来实现，用一个指针 dest 计算如果复写后需要的总长度。
2. 从后向前复制：一旦确定了边界，就可以从后往前将元素复制到正确位置，避免覆盖。

具体流程：

1. 初始化 cur = 0, dest = -1。遍历数组，遇到非零元素 dest 加 1，遇到 0 则 dest 加 2（因为 0 要占两个位置）。
2. 当 dest 达到或超过数组长度时停止。此时 cur 指向的是最后一个参与复写的元素。
3. 检查边界情况：如果 dest 刚好等于数组长度，说明最后一个元素不需要特殊处理；如果 dest 超过了长度，说明最后一个 0 只能复写一次（即数组末尾），需要单独处理。
4. 从 cur 开始向前遍历，根据元素是否为 0，决定是将值写入 dest 还是写入 dest 和 dest-1。

C++ 代码演示

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0;
        int 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--;
        }
    }
};

通过这两道题，我们可以看到双指针在原地修改数组时的灵活性。关键在于理清指针的移动逻辑，尤其是涉及覆盖风险时，反向操作往往能简化问题。