Leetcode刷題日記 - #80. Remove Duplicates from Sorted Array ii

題目請自行上Leetcode閱讀：https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

Sorted Array：只要講到Sorted Array就要知道這跟問題應該跟2 pointer有關聯

Return Value, k：這種題目的關鍵就是k，k指向的就是到目前為止沒有出現超過兩次

這題有點難想，雖然是#26的變化形，整個沒辦法一下子就想出解法

理論上是跟26一樣的，但是現在不能出現兩次，n一定是一直往前進的，那k什麼時候要移動？

當在他之前數字都沒有重複兩次的狀態下

k之前的數字可能會長什麼樣子：

Ex1: [1,1,2]

Ex2: [1,2,3]

Ex3: [1,2,2]

nums[k]和nums[k-1]比起來

如果跟一樣大（如Ex3），nums[k-2]一定是和nums[k]不一樣的數字，不然會重複超過3次

如果跟他不一樣（如Ex1和Ex2），nums[k-2]一定也是和nums[k]不一樣的數字，因為這個是sorted array

這樣想的話，也許可以比較n目前指向的數字，是否與k指向的前兩個數字，也就是nums[k-2]不一樣，就能決定要不要往前，

例如 [1, 1, 1, 2, 2, 3]

k = 2

n = 3

nums[n] = 2, 比較了2與nums[k-2] 不一樣，就可以幫2填進k的位置

[1, 1, 2, 2, 2, 3]，並且移動k

k = 3

n = 4

nums[n] = 2, 比較了2與nums[k-2]不一樣，就可以幫2填進k的位置

[1, 1, 2, 2, 2, 3]，並且移動k

k = 4

n = 5

nums[n] = 3, 比較了3與nums[k-2] 都不一樣，就可以幫3填進k的位置

[1, 1, 2, 2, 3, 3]，並且移動k

k = 5

最後，為了避免index out of bound，記得先確認nums的長度，並且讓k跟n從2開始。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) <= 2:
            return len(nums)
        k = 2
        
        for n in range(2, len(nums)):
            if nums[n] != nums[k-2]:
                nums[k] = nums[n]
                k += 1
            n += 1
        return k

結語：這題的重點在Sorted Array，以及k是指向「沒有兩次以上重複數字」的Sorted Array的尾，但是有點不容易想到condition，但是想k之前長什麼樣子(1, 1, 2) or (1, 2, 3) or (1, 2, 2)，「不重複超過兩次的定義」很有幫助。