80. Remove Duplicates From Sorted Array II

Medium

Description

給定已排序的整數陣列 nums，原地移除重複元素，使每個元素最多出現兩次。回傳結果長度 k。

Example:

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

Intuition#

核心思路：慢指針追蹤寫入位置，只要當前元素不等於 nums[slow - 2]（即允許最多兩個重複），就寫入。

LC 26 的進階版：從「每個最多 1 次」變成「每個最多 2 次」
關鍵判斷條件：與已寫入區域倒數第二個比較，若不同就可以寫入
這個通用模板可以推廣到「最多 k 次」

Approaches#

1: 計數法#

概念: 用計數器追蹤當前元素出現次數，超過 2 次就跳過
時間複雜度: O(n)
空間複雜度: O(1)

class Solution {
    fun removeDuplicates(nums: IntArray): Int {
        if (nums.size <= 2) return nums.size
        var slow = 1
        var count = 1
        for (fast in 1 until nums.size) {
            if (nums[fast] == nums[fast - 1]) {
                count++
            } else {
                count = 1
            }
            if (count <= 2) {
                nums[slow] = nums[fast]
                slow++
            }
        }
        return slow
    }
}

⭐2: Two Pointers（通用模板）#

概念: slow 指向下一個寫入位置；若 nums[fast] != nums[slow - 2]，表示可以再加一個，寫入後推進 slow
時間複雜度: O(n) - 一次遍歷
空間複雜度: O(1) - 原地操作

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

通用模板：若允許最多出現 k 次，條件改為 nums[fast] != nums[slow - k]，初始 slow = k。

🔑 Takeaways#

Pattern: 快慢指針去重（允許 k 個重複）的通用模板
關鍵技巧: 比較 nums[slow - k] 而非計數，讓程式碼更簡潔且可推廣；改 k 值即可處理不同的保留上限