LeetCode 27. Remove Element 詳解

題目：給定陣列 nums 與值 val，原地移除所有等於 val 的元素，返回移除後的新長度。元素順序可以改變，超出新長度的部分無需關心。

範例：nums = [3,2,2,3], val = 3 → 新長度 2，前兩個元素為 [2,2]（順序不限）。

核心思路：快慢雙指針（覆蓋法）

維護兩個指針：

• 慢指針 k：指向下一個可放置「保留元素」的位置，初始 0。
• 快指針 i：遍歷陣列，尋找不等於 val 的元素。

當 nums[i] != val 時，將其複製到 nums[k]，並 k++。遍歷結束後，k 即為新長度。

代碼實現 (C++ / Python / Java)

// C++
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int k = 0;
        for (int x : nums) {
            if (x != val) nums[k++] = x;
        }
        return k;
    }
};

# Python
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        k = 0
        for x in nums:
            if x != val:
                nums[k] = x
                k += 1
        return k

// Java
class Solution {
    public int removeElement(int[] nums, int val) {
        int k = 0;
        for (int x : nums) {
            if (x != val) nums[k++] = x;
        }
        return k;
    }
}

另一種視角：對撞指針（交換法）

若需保持相對順序 不變，上述覆蓋法已是最優。但若順序無關，且 val 出現次數很少，可用首尾指針交換，減少寫入次數：

int removeElement(vector<int>& nums, int val) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        if (nums[left] == val) {
            nums[left] = nums[right--]; // 用尾部元素覆蓋
        } else {
            ++left;
        }
    }
    return left;
}

此法平均寫入次數少，但不保證順序，且需處理交換來的元素仍等於 val 的情況（因此不 left++，下輪再檢查）。

複雜度分析

關鍵點總結

1. 原地修改：不分配新陣列，直接在輸入陣列上操作。
2. 返回長度而非新陣列：評測系統會根據返回長度檢查前 k 個元素。
3. 邊界情況：空陣列、全是 val、無 val 皆能正確處理。
4. 面試延伸：若要求保持相對順序 → 快慢指針；若要求最小化寫入 → 首尾交換。

這道題是「雙指針原地修改陣列」模式的入門典範，同類題目包括 LeetCode 26 Remove Duplicates from Sorted Array、283 Move Zeroes、844 Backspace String Compare 等，掌握此模式可輕鬆應對一大類原地陣列操作問題。