26. Remove Duplicates From Sorted Array

解法已隱藏 — 先讀題目敘述、自己想想看，再點上方按鈕揭曉。

26Remove Duplicates From Sorted ArrayTwo PointersEasyTwo Pointers

給定已排序的整數陣列 nums，原地移除重複元素，使每個元素只出現一次。回傳不重複元素的數量 k，且 nums 的前 k 個位置為不重複元素。

Example:

Input: nums = [1,1,2] Output: 2, nums = [1,2,_]

Intuition

TIP

核心思路：慢指針記錄不重複元素的尾端位置，快指針掃描陣列，遇到新值就寫入慢指針位置。

陣列已排序，所以重複元素一定相鄰
快慢指針模式：快指針跳過重複，慢指針負責寫入

Approaches

1. Use a HashSet — O(n) / O(n)

Idea: 用 Set 去重，再寫回陣列
Time: O(n)
Space: O(n) - Set 儲存

HashSet Code

class Solution {
    fun removeDuplicates(nums: IntArray): Int {
        val set = linkedSetOf<Int>()
        for (num in nums) set.add(num)
        var i = 0
        for (num in set) nums[i++] = num
        return set.size
    }
}

⭐ 2. Two Pointers (Fast & Slow) — O(n) / O(1)

Idea: slow 指向最後一個不重複元素的位置，fast 掃描每個元素；當 nums[fast] != nums[slow] 時，將值寫入 slow + 1
Time: O(n) - 一次遍歷
Space: O(1) - 原地操作

class Solution {
    fun removeDuplicates(nums: IntArray): Int {
        if (nums.isEmpty()) return 0
        var slow = 0
        for (fast in 1 until nums.size) {
            if (nums[fast] != nums[slow]) {
                slow++
                nums[slow] = nums[fast]
            }
        }
        return slow + 1
    }
}

WARNING

slow 指向的是「最後一個已寫入的位置」，所以回傳 slow + 1。注意與 LC 80（允許出現兩次）的差異。

🔑 Takeaways

Pattern: 快慢指針去重，利用已排序的特性
Key trick: slow 代表已處理結果的尾端，fast 負責發現新值；這個模板可以推廣到 LC 80（保留最多 k 個重複）

Intuition

Approaches

🔑 Takeaways

相關題目