LeetCode 26. 刪除有序數組中的重複項：快慢指針去重

LeetCode 26. 刪除有序數組中的重複項：快慢指針去重

給定已排序數組，原地刪除重複元素使每個元素只出現一次，返回新長度。O(1) 額外空間。

快慢指針算法

• j 指向當前不重複部分的最後一個元素（初始 0）。
• i 遍歷數組，當 nums[i] != nums[j] 時，++j; nums[j] = nums[i]。
• 最終新長度 = j + 1。

代碼實現

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

執行示例

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

關鍵點

1. 利用有序性：重複元素必相鄰，只需比較相鄰不同元素。
2. j 初始為 0，循環從 i=1 開始，避免自我比較。
3. 空數組單獨處理返回 0。

複雜度

• 時間 O(n)，空間 O(1)。

延伸：允許最多保留 k 個重複

修改判斷條件為 nums[i] != nums[j-k+1] 即可（LeetCode 80）。