LeetCode 經典：有序數組去重雙指針法原理與擴展（保留 k 個重複）

有序數組去重：原地修改 O(1) 空間最優解

給定已排序數組，要求原地移除重複元素，返回新長度。LeetCode 26/80 題核心模式，雙指針法是標準解法。

基礎版：保留單個唯一值 (LeetCode 26)

public static int removeDuplicates(int[] nums) {
    if (nums.length < 2) return nums.length;
    
    int slow = 1; // 指向下一個不重複元素應放置的位置
    for (int fast = 1; fast < nums.length; fast++) {
        // 發現新值：nums[fast] != 已確定區域最後一個值 nums[slow-1]
        if (nums[fast] != nums[slow - 1]) {
            nums[slow++] = nums[fast]; // 放入並推進 slow
        }
    }
    return slow; // 新長度
}

執行流程圖解

初始: [1, 1, 2, 2, 3]
       ↑  ↑
      s=1 f=1

f=1: nums[1]=1 == nums[0] → 跳過
f=2: nums[2]=2 != nums[0] → nums[1]=2, s=2
     [1, 2, 2, 2, 3]
f=3: nums[3]=2 == nums[1] → 跳過
f=4: nums[4]=3 != nums[1] → nums[2]=3, s=3
     [1, 2, 3, 2, 3] → 返回 3，前 3 位為去重結果

進階版：保留至多 k 個重複 (LeetCode 80)

public static int removeDuplicatesK(int[] nums, int k) {
    if (nums.length <= k) return nums.length;
    
    int index = k; // 前 k 個直接保留
    for (int i = k; i < nums.length; i++) {
        // 比較當前值與「已確定區域倒數第 k 個」
        if (nums[i] != nums[index - k]) {
            nums[index++] = nums[i];
        }
    }
    return index;
}

k=2 示例

輸入: [1,1,1,2,2,3]
index=2
i=2: nums[2]=1 == nums[0] → 跳過
i=3: nums[3]=2 != nums[0] → nums[2]=2, index=3
i=4: nums[4]=2 != nums[1] → nums[3]=2, index=4
i=5: nums[5]=3 != nums[2] → nums[4]=3, index=5
結果: [1,1,2,2,3,...] 長度 5

核心不變量

• nums[0..slow-1] / nums[0..index-1] 始終維護「已處理的合法結果區」
• fast / i 為掃描指針，遍歷原始數據
• 比較基準始終來自「結果區」尾部，利用有序性保證正確性

複雜度分析

擴展場景

1. 無序數組去重：先排序 O(n log n) 或用 HashSet O(n) 空間
2. 鏈表去重：同樣雙指針，prev.next = curr.next 刪除節點
3. 字符串去重：轉 char[] 處理後 new String(arr, 0, len)
4. 流式數據：若無法隨機訪問，需 HashSet 記錄已見值

面試加分點

• 能手寫無 Bug 邊界條件（空數組、單元素、全重複）
• 能推廣到 k 重複版本並解釋 index - k 幾何含義
• 能說明為什麼 slow 初始為 1 而非 0
• 了解 System.arraycopy 批量移動優化大數據場景

雙指針是陣列/鏈表原地修改問題的萬能鑰，熟練掌握此模式可秒殺大量 LeetCode Easy/Medium 題。