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

二、复写零

题目链接

1. 题目描述

2. 核心思路

复写零比移动零稍复杂，因为直接在原数组上操作会覆盖后续元素。为了避免数据丢失，我们采用'两次遍历'的策略：先定位，后写入。

第一步：定位 模拟复写过程，计算如果进行复写，最终的有效长度会延伸到哪里。

• cur：遍历原数组。
• dest：跟踪在新数组中的目标位置。
• 规则：遇到非零元素，dest 移动 1 位；遇到零元素，dest 移动 2 位。
• 终止条件：当 dest 达到或超过数组末尾时停止。此时 cur 即为最后一个需要处理的元素索引。

第二步：写入 从后向前进行复制，避免覆盖未处理的数据。

• 遇到非零元素：直接复制到 dest 位置。
• 遇到零元素：在 dest 位置写入两个零。

边界处理： 如果最后一个零恰好导致 dest 超出数组边界，说明这个零只能写入一个。此时需要在数组末尾补一个零，并调整指针回退。

3. 代码实现

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0, dest = -1, n = arr.size();
        
        // 1. 寻找最后一个需要复写的元素位置
        while (cur < n) {
            if (arr[cur]) 
                dest++;
            else 
                dest += 2;
            
            if (dest >= n - 1) break;
            cur++;
        }
        
        // 2. 处理边界情况：如果最后一个零导致越界
        if (dest == n) {
            arr[n - 1] = 0;
            cur--;
            dest -= 2;
        }
        
        // 3. 从后向前复写
        while (cur >= 0) {
            if (arr[cur]) 
                arr[dest--] = arr[cur--];
            else {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
};