80. Remove Duplicates from Sorted Array II

📘 題目敘述

給定一個已排序（非遞減）的整數陣列 nums，請你原地修改陣列，使得每個元素最多只出現兩次。

修改後回傳新的長度 k，並保證：

nums 的前 k 個元素符合條件
不需要考慮 k 之後的元素
必須使用 O(1) 額外空間

條件限制

1 ≤ nums.length ≤ 3 * 10^4
-10^4 ≤ nums[i] ≤ 10^4
nums 已依非遞減順序排序

🧠 解題思路

這題的關鍵不是「刪除」，而是：用一個寫入指標，把合法的數字往前覆蓋。

因為陣列已排序，所以相同的數一定連續出現，我只需要記錄當前數字出現的次數。

策略是一路掃描 nums：

第一次出現 → 一定保留
第二次出現 → 也保留
第三次（含以後） → 不寫入

所有變數

now：目前正在處理的數字，用來判斷是否和前一個一樣
count：記錄目前這個數字已經連續出現幾次
pos：寫入位置指標，指向下一個合法元素應該寫到哪
a：for-each 迴圈中掃描到的元素值

🪜 主要流程步驟

1. 初始化狀態

now 先設成一個不可能出現的值（例如 20000）
count = 1
pos = 0

確保第一個元素一定會被當作新數字處理。

2. 逐一掃描陣列元素

用 for (int a : nums) 逐一掃描原陣列。

情況一：`a != now`（遇到新數字）

重設 count = 1
更新 now = a
寫入 nums[pos] = a，並 pos++

新數字第一次出現，一定要保留。

情況二：`a == now`（重複數字）

count++
只有在 count == 2 時才寫入
第三次以上直接忽略

3. 掃描結束

pos 就是新的有效長度
nums[0 .. pos-1] 即為答案陣列

💡 為什麼這樣一定正確？

陣列已排序，相同數字必定連續出現
count 只在同一數字區段內累加
每個數字最多只會被寫入兩次
不需要真的刪元素，只控制寫入位置

時間複雜度是 O(n)，空間複雜度是 O(1)。

💻 程式碼實作

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int now = 20000;
        int count = 1;
        int pos = 0;
        for (int a : nums) {
            if (a != now) {
                count = 1;
                now = a;
                nums[pos] = a;
                pos++;
            } else {
                count++;
                if (count == 2) {
                    nums[pos] = now;
                    pos++;
                }
            }
        }
        return pos;
    }
};

🔗 題目連結

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/