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

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--;
        }
    }
};

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