283.移动零

stack, two pinters, https://leetcode.cn/problems/move-zeroes/

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

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

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示:

• 1 <= nums.length <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1

进阶：你能尽量减少完成的操作次数吗？

思路：快慢指针。维护一个最左边的空位（慢指针 i0），用一个快指针 i 遍历数组。

from typing import List

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        n = len(nums)
        i0 = 0  # 慢指针，指向最左边的空位
        for i in range(n):  # 快指针，扫描整个数组
            if nums[i] != 0:
                if i != i0:  # 只有当 i > i0 时才需要交换
                    nums[i0], nums[i] = nums[i], nums[i0]
                i0 += 1

直接维护 i0，只要发现非零元素就交换到前面。i != i0 时才交换，避免了无意义的自交换。

逻辑只分为两步——遇到非零 → 放到最左空位 → 更新 i0， 非零元素只动一次（要么本身不动，要么交换到正确位置），时间复杂度 O(n)，空间 O(1)。

from typing import List

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        n = len(nums)
        left = 0   # 慢指针，指向最左边的空位
        right = 0  # 快指针，扫描整个数组

        while right < n:
            if nums[right] != 0:   # 找到非零元素
                if left != right:  # 只有当 left < right 才需要交换
                    nums[left], nums[right] = nums[right], nums[left]
                left += 1          # 更新最左空位
            right += 1             # 快指针继续扫描