LeetCode 283. 移动零 | C++ 双指针原地操作题解

📌 题目描述

题目级别：简单

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

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

💡 解题思路：快慢双指针 (Two Pointers)

这道题的难点在于原地操作和保持相对顺序。如果我们遇到 0 就把它删掉再加到尾部，不仅操作繁琐，而且底层数组元素的频繁搬移会导致时间复杂度飙升到 $O(N^2)$。

最高效的做法是使用同向双指针：

1. 慢指针 l：记录“下一个非零元素应该安放的正确位置”。
2. 快指针 i：负责在前面探路，遍历整个数组。

核心逻辑：
当快指针 i 遇到一个非零元素时，我们就把它和慢指针 l 指向的元素进行交换（swap）。

• 交换完之后，l 顺势向前走一步（l++），准备迎接下一个非零元素。
• 这样操作的神奇之处在于：无论快指针在前面扫过多少个 0，只要它遇到非零数，就会通过交换把它扔回给慢指针。最终，所有的非零元素被按原序排在了数组前面，而所有的 0 则被自然而然地“置换”到了数组的后面！

💻 C++ 代码实现

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int l = 0; // 慢指针，记录下一个非零元素应该存放的位置
        
        // i 为快指针，遍历整个数组
        for (int i = 0; i < nums.size(); i++) {
            // 如果遇到非零元素，将其与慢指针位置的元素交换，同时慢指针前进
            if (nums[i] != 0) {
                swap(nums[l++], nums[i]); 
            }
        }
    }
};