26. Remove Duplicates from Sorted Array

──────────────────────────────────────────────────────────────────────

題目的標題寫的並不是很清楚，這個題目其實是要把不重複的值依序搬到陣列的前段，然後回傳「不重複元素的個數」k。至於第 k 格之後留下什麼垃圾，題目完全不管。

會覺得題目讀起來怪，是因為它同時要兩件事：一個回傳值（k），和一個副作用（原地改動前 k 格）。大部分題目只要其中一個。

思路

關鍵在題目名稱裡那三個字：Sorted。

已排序代表重複的值一定相鄰。這句話直接決定了解法：我不需要記住「哪些值出現過」，只需要比較「當前這個值」和「上一個我決定保留的值」——兩者不同就是遇到新值了。

面試時我會照這個順序講，因為它剛好展示了「排序」這個條件的價值：

如果沒有排序，我會用一個 set 記住出現過的值， $O (n)$ 時間但要 $O (n)$ 空間。
但既然已經排序，重複必相鄰，我只要跟前一個保留的值比就好——降到 $O (1)$ 空間，而且不用額外容器。

講出第 2 句就等於答出這題想考的東西了。反過來說，如果一開始就直接寫雙指針而沒說明為什麼可以，面試官會不確定你是想通了還是背過。

解題方向

兩個指針各有明確的語意，先定義清楚再動手：

slow——已去重區間的最後一格索引，也就是「目前為止最後一個我決定保留的值」在哪
fast——掃描指針，單向走過整個陣列

於是 nums[fast] != nums[slow] 讀起來就是「我遇到一個和保留區尾端不同的值」，那就把 slow 往前挪一格，把新值寫進去。相等的時候什麼都不做，fast 自己往前走——那一格會被後面的新值覆蓋掉。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow = 0
        fast = 0

        while fast < len(nums):
            if nums[fast] != nums[slow]:
                slow += 1
                nums[slow] = nums[fast]
            fast += 1

        return slow + 1

最後回傳 slow + 1 而不是 slow：slow 是索引，長度是索引加一。這個 off-by-one 是這題最容易寫錯的地方，寫完後拿 [1, 1, 2] 手動跑一遍最快——slow 停在 1，答案是 2。

補充

空陣列：這份程式碼在 nums 為空時會回傳 1（迴圈一次都沒進，slow 還是 0）。LeetCode 這題的約束是 1 <= nums.length，所以線上不會踩到。要處理的話加一行：

if not nums:
    return 0

另一種等價寫法：常見的版本會寫 nums[fast] != nums[fast - 1]。兩種都對，差別在比較的對象——我這版比的是「保留區的尾端」，另一版比的是「原陣列的前一格」。因為只有相等時才不寫入，這兩個值在這題裡永遠一致；但換成別的變形題（例如允許重複兩次）就不一定，所以我習慣比保留區的尾端，語意比較不會混。

同一個模式的題目：283. Move Zeroes（把 0 往後擠）用的是完全一樣的骨架，只有「什麼情況要寫入」那個條件不同。27. Remove Element 也能用這個骨架寫，但那題的敘述明說「順序不拘」，所以還有一種把要移除的值直接跟尾端交換的解法 —— 要移除的元素很少時寫入次數少得多。三題都見 Two Pointers 模板。

複雜度

時間 $O (n)$ — fast 單向走完陣列，每格只看一次
空間 $O (1)$ — 只用兩個索引變數，原地覆寫，沒有額外容器

其中 $n$ 是陣列長度。