Intuition#

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

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

Approaches#

1: 使用 HashSet#

• 概念: 用 Set 去重，再寫回陣列
• 時間複雜度: O(n)
• 空間複雜度: O(n) - Set 儲存

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（快慢指針）#

• 概念: slow 指向最後一個不重複元素的位置，fast 掃描每個元素；當 nums[fast] != nums[slow] 時，將值寫入 slow + 1
• 時間複雜度: O(n) - 一次遍歷
• 空間複雜度: 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
    }
}

🔑 Takeaways#

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