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

在学习了基础语法之后，是时候通过实际题目来巩固一下双指针技巧了。今天我们来拆解两道经典的数组原地操作题：移动零与复写零。

一、移动零

题目描述

给定一个数组 nums，要求将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。注意，必须在原数组上操作，不能创建新数组。

思路解析

这道题的核心在于如何在不破坏原有顺序的前提下完成交换。最直观的想法是创建一个新数组，但这违反了空间复杂度的要求。

我们可以使用两个指针：

• current（快指针）：负责遍历整个数组，寻找非零元素。
• dest（慢指针）：指向当前应该放置非零元素的位置。

当 current 遇到非零元素时，将其与 dest 位置的元素交换，然后 dest 向后移动一位。无论是否交换，current 都会继续向前。这样就能保证所有非零元素按顺序被'挤'到前面，剩下的位置自然就是 0。

代码实现

void Swap(int *a, int *b) {
    int temp = 0;
    temp = *a;
    *a = *b;
    *b = temp;
}

void moveZeroes(int* nums, int numsSize) {
    int current = 0;
    int dest = 0;
    while (current < numsSize) {
        if (nums[current] != 0) {
            Swap(nums + dest, nums + current);
            dest++;
        }
        current++;
    }
}

这段逻辑在力扣等平台上提交均能通过。关键点在于 Swap 函数保证了非零元素的相对顺序不被打乱。

二、复写零

题目描述

给定一个固定长度的整数数组 arr，将数组中出现的每个 0 都复写一遍，其余元素向右移动。超出数组长度的元素将被丢弃。

思路解析

如果从前往后遍历并插入 0，后面的元素会被不断覆盖，导致数据丢失。因此，正确的策略是从后往前处理。

具体步骤如下：

1. 确定写入边界：先遍历一次数组，计算如果进行复写操作，最后一个有效元素会落在哪里。这决定了我们倒序复制的起始点。
2. 处理边界情况：如果最后一个被复写的元素恰好是 0，且它会导致数组越界（即原本该位置是 0，复写后多出一个 0），则需要特殊处理，丢弃末尾的一个元素。
3. 倒序复制：从确定的边界开始，向前遍历原数组。遇到 0 就写入两次，遇到非零元素则写入一次。

代码实现

void duplicateZeros(int* arr, int arrSize) {
    // 第一步：找出最后被复写到的位置
    int cur = 0;
    int dest = -1;
    while (cur < arrSize) {
        if (arr[cur]) {
            dest++;
        } else {
            dest += 2;
        }
        if (dest >= arrSize - 1) break;
        cur++;
    }

    // 判断边界情况：如果倒数第二个元素是 0，会导致多出一个 0 被截断
    if (dest == arrSize) {
        arr[arrSize - 1] = 0;
        cur--;
        dest -= 2;
    }

    // 第二步：从后向前实现复写操作
    while (cur >= 0) {
        if (arr[cur] == 0) {
            arr[dest--] = 0;
            arr[dest--] = 0;
        } else {
            arr[dest--] = arr[cur];
        }
        cur--;
    }
}

通过这种倒序填充的方式，我们完全避免了覆盖尚未处理的元素，确保了算法的正确性和效率。