283 移动零

一、题目

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

二、题解

思路： 双指针（覆盖写入 + 补零）。

• 慢指针 slow 记录下一个非零元素该放的位置，快指针 i 扫描整个数组。
• i 每遇到一个非零元素，就把它写到 slow 处并 slow++，使所有非零元素按原相对顺序前移。
• 扫描结束后，从 slow 到末尾全部填 0 即可，全程原地操作。

class Solution {
    public void moveZeroes(int[] nums) {
        // 【定义慢指针】slow 专门用来记录“下一个非零元素应该存放的坑位”
        int slow = 0;

        // 【快指针 i 负责全盘扫描】遍历整个数组
        for (int i = 0; i < nums.length; i++) {

            // 核心逻辑：只要发现当前考察的数字不是 0
            if (nums[i] != 0) {
                // 就把它按顺序“塞”进 slow 指向的坑位里
                nums[slow] = nums[i];
                // 坑位被填上了，slow 往前挪一步，准备迎接下一个非零元素
                slow++;
            }
        }

        // 【善后收尾】
        // 当上面的循环结束时，所有的非零元素都已经按原本的顺序挤到了数组最前面。
        // 此时 slow 指针所在的位置，以及它后面的所有位置，理所应当全都是 0，直接批量填平即可。
        for(int i = slow; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

时间复杂度：$O(n)$（两次线性遍历数组）

空间复杂度：$O(1)$（原地操作，只用常数个指针变量）