LeetCode 27 Remove Element - 移除指定值並返回新長度

題目翻譯

給定一個數組 nums 和一個值 val，原地移除所有等於 val 的元素，返回移除後的新長度。元素順序可以改變，不需要維護超出新長度的部分。

雙指針法（標準解法）

使用兩個指針：slow 指向下一個要放置非目標值的位置，fast 遍歷數組。當 nums[fast] != val 時，將其賦值給 nums[slow] 並遞增 slow。最後 slow 即為新長度。

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

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

// Java
public class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
}

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

另一種思路：與尾部元素交換

若目標值較少，可用頭尾雙指針：left 從頭掃描，right 從尾縮減。當 nums[left] == val 時，用 nums[right] 覆蓋並 right--；否則 left++。這樣最多只需交換目標值的次數，但順序會被打亂（題目允許）。

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;
}

複雜度分析

• 時間：O(n) — 單次遍歷。
• 空間：O(1) — 原地修改，常數額外空間。

總結

本題是雙指針技巧的入門級應用。「快慢指針」穩定、易理解，適合大多數場景；「頭尾交換」在目標值稀少時賦值次數更少。面試中先寫快慢指針版，再補充頭尾交換優化，展示對不同數據分佈的考慮。