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

算法总结

这个解法本质上就是快速排序单趟划分过程的变体。通过维护一个边界指针，我们实现了 O(N) 的时间复杂度和 O(1) 的空间复杂度。实际运行时，注意 dest 的更新时机，确保它始终指向待填充的非零位置。

02、复写零

题目来源：LeetCode 1089. Duplicate Zeros

题目描述

给定一个固定长度的整数数组 arr，将数组中出现的每个 0 都复写一遍，并将其余元素向右平移。注意：超出原数组长度的元素不再写入。

算法思路

如果直接从前往后原地复写，后面的数据会被覆盖掉。因此，我们需要采用从后往前的策略。但为了知道从哪里开始复写，我们需要先确定最终的有效长度范围。

整体分为两步：

1. 统计阶段：找到最后一个需要复写的元素位置。
2. 填充阶段：从后向前进行复制。

算法流程

第一步：确定边界

使用 cur 扫描原数组，dest 模拟复写后的索引位置。

• 若 arr[cur] 为 0，dest 增加 2（因为要占两个位置）。
• 否则，dest 增加 1。
• 当 dest 达到或超过数组长度时停止，此时 cur 即为最后一个参与复写的元素下标。

第二步：处理越界

如果 dest 刚好等于数组长度，说明最后一个 0 复写时会超出边界。这种情况下，数组最后一个位置必须手动置为 0，且 cur 需要回退一步，dest 回退两步，以便后续逻辑正确执行。

第三步：从后向前填充

从 cur 开始倒序遍历：

• 如果是 0，在 dest 和 dest-1 处填入 0，指针各减 2。
• 如果不是 0，在 dest 处填入该值，dest 减 1。
• cur 减 1，继续循环直到处理完所有元素。

C++ 代码演示

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int dest = -1;
        int cur = 0;
        int n = arr.size();

        // 1. 找到最后一个复写的数
        while (true) {
            dest++;
            if (arr[cur] == 0) {
                dest++; // 0 会占用两个位置
            }
            if (dest >= n - 1) {
                break;
            }
            cur++;
        }

        // 2. 处理越界情况
        // 如果 dest 刚好等于 n，说明最后一个 0 复写时超出了数组边界
        if (dest == n) {
            arr[n - 1] = 0;
            dest -= 2;
            cur--;
        }

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

算法总结及流程解析

这个解法的关键在于避免数据覆盖。通过两次遍历，第一次确定边界，第二次安全回填，确保了 O(N) 的时间效率。特别注意 dest 越界的判断，这是最容易出错的地方。如果最后一个元素是 0 且复写后刚好溢出，必须单独处理数组末尾。