---
title: "26. Remove Duplicates from Sorted Array"
url: "https://laigary.com/interview/coding/26-remove-duplicates-from-sorted-array"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-25"
tags: ["Two Pointers"]
---

# 26. Remove Duplicates from Sorted Array

[26\. Remove Duplicates from Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array/)

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

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

## 思路

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

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

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

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

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

## 解題方向

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

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

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

```python
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`，所以線上不會踩到。要處理的話加一行：

```python
if not nums:
    return 0
```

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

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

## 複雜度

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

其中 $n$ 是陣列長度。