算法题精讲：双指针法解决移动零与复写零

算法总结： 这里用到的方法正是数据结构中快排算法单趟的核心步骤——数据划分。理解这一点有助于举一反三，处理更多类似的分区问题。

复写零

题目链接： 1089. 复写零 - LeetCode

题目描述： 给定一个固定长度的整数数组 arr，将数组中出现的每个零都复写一遍，并将其余元素向右平移。注意：不能在超出该数组长度的地方写入元素，且必须在原数组上进行操作。

题目示例： 输入：[1,0,2,3,0,4,5,0] 输出：[1,0,0,2,3,0,0,4]

解法思路： 如果从前往后进行原地复写操作，由于 0 的出现会复写两次，导致后续没有复写的数被覆盖掉。因此我们选择从后往前的复写策略。 但是从后往前复写的时候，我们需要找到最后一个复写的数在哪里。大体流程分为两步：先找到最后一个复写的数，然后从后往前进行复写操作。

算法流程：

1. 初始化两个指针 cur = 0，dest = -1。
2. 找到最后一个复写的数：
   • 判断 cur 位置的元素：如果是 0，dest 往后移动两位；否则，dest 往后移动一位。
   • 判断 dest 是否已经到达结束位置，如果结束就终止循环。
   • 如果没有结束，cur++，继续判断。
3. 判断 dest 是否越界到 n 的位置：
   • 如果越界，执行下面三步：n-1 位置的值修改成 0；cur 向前移动一步（cur--）；dest 向前移动两步（dest -= 2）。
   • 之所以会越界，是因为如果最后一个复写的数为 0，可能出现复写的位置在下标 n-1 和 n，但下标为 n 就是越界。实际上并没有复写两遍 0，而只是数组最后一个位置复写为 0。所以如果越界操作就是数组最后位置手动置为 0 后让 dest 回到倒数第二个位置，cur-- 就是让最后一个复写的数变成前一个。
4. 从 cur 位置开始往前遍历原数组，依次还原出复写后的结果数组：
   • 判断 cur 位置的值：如果是 0，dest 以及 dest-1 位置修改成 0，dest-=2；如果非零，dest 位置修改成 0，dest -= 1。
   • cur--，复写下一个位置。

C++ 代码演示：

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        // 1. 先找到最后一个复写的数
        int dest = -1;
        int cur = 0;
        while(1) {
            dest++;
            if(arr[cur] == 0) {
                dest++;
            }
            if(dest >= arr.size() - 1) {
                break;
            }
            cur++;
        }

        // 2. 处理越界情况
        if(dest == arr.size()) {
            arr[arr.size() - 1] = 0;
            dest -= 2;
            cur--;
        }

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

算法总结及流程解析： 通过两次遍历，第一次确定有效长度，第二次反向填充，既保证了空间复杂度 O(1)，又避免了数据覆盖的问题。