LeetCode 26 移除有序數組重複項：雙指針原地修改

LeetCode 26 移除有序數組重複項：雙指針原地修改

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

雙指針算法

• slow 指向當前不重複部分的末尾（下一個唯一值的寫入位置）。
• fast 遍歷數組。
• 若 nums[fast] != nums[slow]，則 slow++，nums[slow] = nums[fast]。

最終新長度 = slow + 1。

代碼

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

擴展：無序數組去重

• 不允許額外空間：先排序（快排 O(n log n)），再用上述方法。
• 允許額外空間：用 HashSet 記錄已見元素，O(n) 時間，O(n) 空間。

本題關鍵在於利用「已排序」特性，線性掃描即可完成去重。