LeetCode 原地复写零：双指针逆向填充 O(n) 最优解

一、问题背景

这道题要求在一个固定长度的数组中，将每个出现的 0 复写一遍，并将后续元素向右移动。关键约束是必须在原数组上修改（原地操作），且不能使用额外的数组空间。

如果直接从前向后遍历并插入 0，后面的元素会被覆盖，导致数据丢失。因此，我们需要一种策略来避免这种冲突，核心思路是先确定边界，再从后往前填充。

二、思路分析

1. 确定复写边界

我们使用两个指针：cur 用于遍历原数组，pre 模拟复写后的逻辑位置。

• 当 arr[cur] 不为 0 时，pre 向前移动一位；
• 当 arr[cur] 为 0 时，pre 向前移动两位（因为 0 需要占据两个位置）；
• 一旦 pre 超出或等于数组长度 n，说明已经找到了最后一个需要处理的元素，停止遍历。

这里有一个特殊的边界情况：如果 pre 恰好等于 n，说明最后一个被复写的元素是 0，它占据了数组的最后一位，而前一位不需要再写入。此时需要将数组最后一位强制设为 0，并调整指针回退。

2. 逆向填充

确定了边界后，我们从 cur 指向的位置开始，从后向前遍历原数组，将元素复制到 pre 指向的位置。

• 如果当前元素不是 0，直接赋值给 arr[pre]，然后 cur 和 pre 同时减一；
• 如果当前元素是 0，则需要在 arr[pre] 和 arr[pre-1] 处都写入 0，然后 cur 减一，pre 减二。

这种方式保证了在写入新数据时，不会覆盖掉后面还未读取的原数据。

三、代码实现

class Solution {
    public   {
           , pre = -, n = arr.length;

        
         (cur < n) {
             (arr[cur] == ) {
                pre += ;
            }  {
                pre++;
            }
             (pre >= n - ) {
                ;
            }
            cur++;
        }

        
         (pre == n) {
            arr[n - ] = ;
            cur--;
            pre -= ;
        }

        
         (cur >= ) {
             (arr[cur] != ) {
                arr[pre--] = arr[cur--];
            }  {
                arr[pre--] = ;
                arr[pre--] = ;
                cur--;
            }
        }
    }
}