LeetCode 27. 移除元素：雙指針原地刪除詳解

LeetCode 27. 移除元素：雙指針原地刪除詳解

給定數組 nums 和值 val，原地移除所有等於 val 的元素，返回新長度。不需保持順序，超出新長度部分內容無關緊要。

雙指針核心思路

• 快指針 i：遍歷原數組每個元素。
• 慢指針 j：指向下一個可放置非 val 元素的位置。
• 當 nums[i] != val 時，nums[j++] = nums[i]。

代碼實現

int removeElement(int* nums, int numsSize, int val) {
    int j = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] != val) {
            nums[j++] = nums[i];
        }
    }
    return j;
}

執行過程示例

nums = [3,2,2,3], val = 3
i=0: nums[0]=3 == val → skip
i=1: nums[1]=2 != val → nums[0]=2, j=1
i=2: nums[2]=2 != val → nums[1]=2, j=2
i=3: nums[3]=3 == val → skip
返回 j=2, nums 前兩位為 [2,2]

複雜度

• 時間 O(n) —— 單次遍歷。
• 空間 O(1) —— 只用兩個整型變量。

變體：保持相對順序

上述算法已天然保持非 val 元素的相對順序。若題目要求移除後元素順序不變，同樣適用。

對比：原文雙循環寫法

// 原文：先計數再搬移，兩次遍歷
int k = 0;
for (i = 0; i < numsSize; i++) if (val == nums[i]) k++;
for (i = 0; i < numsSize; i++) if (val != nums[i]) nums[j++] = nums[i];

雖然正確，但單循環版本更簡潔高效，是面試首選寫法。