[Leetcode解題] 659. Split Array into Consecutive Subsequences

30 October 2026

medium array greedy hash-table

題目

659. Split Array into Consecutive Subsequences

給定一個已按照非遞減順序排列的整數陣列 nums，判斷能否將所有元素分配到一個或多個子序列，使每個子序列都符合：

相鄰數字恰好相差 1，例如 [2, 3, 4]。
長度至少為 3。

每個位置的元素都必須使用一次。子序列可以跳過原陣列中的其他元素，但必須保持原本的相對順序；不需要是連續的子陣列。

題目限制：1 <= nums.length <= 10^4，-1000 <= nums[i] <= 1000，且輸入已排序。

解題思路

1. 從小到大處理，每個數字有兩種去處

由於陣列已排序，我們可以依序處理每個尚未使用的數字 x。

要讓 x 出現在合法的連續序列中，可以：

接在以 x - 1 結尾的既有序列後面。
當作新序列的起點，同時使用 x + 1、x + 2，建立 [x, x + 1, x + 2]。

第二種做法直接建立長度為 3 的序列，避免留下長度不足、之後還必須補齊的序列。因此，演算法建立的每個序列從一開始就是合法的。

如果兩種方式都做不到，就無法安置目前的 x，回傳 false。

2. 為什麼優先延長既有序列？

建立新序列會額外消耗後面的兩個數字，延長既有序列則只需要目前的 x。當兩種方式都可行時，優先延長可以保留後續數字的使用彈性。

例如：

nums = [1, 2, 3, 4, 5, 5, 6, 7]

建立 [1, 2, 3] 後，處理 4 時有兩種選擇：

優先延長：得到 [1, 2, 3, 4]，剩下的 [5, 5, 6, 7] 可以分成一個延長用的 5，以及新序列 [5, 6, 7]。
優先開新序列：建立 [4, 5, 6] 後，剩下 [5, 7]，其中的 5 既不能接在任何序列後，也無法建立 [5, 6, 7]。

因此，不能只要湊得到三個數字，就急著建立新序列。

3. 用兩張表記錄剩餘數字與序列的結尾

我們不需要真的儲存每條序列，只需要知道哪些數字還能使用，以及有多少條序列可以接上目前的數字。

定義：

狀態	意義
`count[x]`	尚未使用的數字 `x` 有幾個
`tail[x]`	有幾條已合法的序列，以 `x` 結尾

例如 [1, 2, 3] 建立後，便令 tail[3] += 1。

tail 直接記錄序列最後一個數字。要加入 x，就檢查 tail[x - 1] 是否大於零。這些序列都已經至少有三個元素，隨時結束都合法。

處理 x 時，先檢查 count[x]。如果是 0，代表這個值的所有副本都已使用，直接跳過。

否則先消耗一個 x，再依照以下順序處理：

情況一：tail[x - 1] > 0，延長既有序列。

tail[x - 1] -= 1
tail[x] += 1

原本以 x - 1 結尾的一條序列，延長後改成以 x 結尾。

情況二：沒有序列可以接 x，但還有 x + 1 與 x + 2。

count[x + 1] -= 1
count[x + 2] -= 1
tail[x + 2] += 1

建立 [x, x + 1, x + 2]，因此以 x + 2 結尾的序列數量增加一。

情況三：以上都不成立。

目前的 x 無法加入任何合法序列，回傳 false。

範例推演

使用包含重複數字的例子：

nums = [1, 2, 3, 3, 4, 4, 5, 5]

初始化 count 後，tail 為空。以下只列出尚有數量的狀態：

走訪的值	動作	動作後的 count	動作後的 tail
1	建立 `[1, 2, 3]`	`{3: 1, 4: 2, 5: 2}`	`{3: 1}`
2	已使用，跳過	`{3: 1, 4: 2, 5: 2}`	`{3: 1}`
第一個 3	建立 `[3, 4, 5]`	`{4: 1, 5: 1}`	`{3: 1, 5: 1}`
第二個 3	已使用，跳過	`{4: 1, 5: 1}`	`{3: 1, 5: 1}`
第一個 4	延長 `[1, 2, 3]`	`{5: 1}`	`{4: 1, 5: 1}`
第二個 4	已使用，跳過	`{5: 1}`	`{4: 1, 5: 1}`
第一個 5	延長 `[1, 2, 3, 4]`	`{}`	`{5: 2}`
第二個 5	已使用，跳過	`{}`	`{5: 2}`

最後分成 [1, 2, 3, 4, 5] 與 [3, 4, 5]，回傳 true。tail[5] = 2 表示有兩條以 5 結尾的合法序列，不需要再出現 6。

再看失敗的例子：

nums = [1, 2, 3, 4, 4, 5]

先建立 [1, 2, 3]，再用第一個 4 延長成 [1, 2, 3, 4]。第二個 4 無法接在既有序列後面；若要建立 [4, 5, 6]，又缺少 6，因此回傳 false。

演算法步驟

統計所有數字的出現次數，存入 count，並建立空的 tail。
按照輸入順序走訪 x；若 count[x] == 0，直接跳過。
將 count[x] 減一。
若 tail[x - 1] > 0，延長既有序列，更新 tail[x - 1] 與 tail[x]。
否則，若 x + 1、x + 2 仍有剩餘，消耗它們建立新序列，並增加 tail[x + 2]。
若兩種方式都失敗，回傳 false；所有數字處理完後回傳 true。

C++ 實作

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, int> count;
        unordered_map<int, int> tail;
        for (int x : nums) {
            count[x]++;
        }

        for (int x : nums) {
            if (count[x] == 0) continue;
            count[x]--;

            if (tail[x - 1] > 0) {
                tail[x - 1]--;
                tail[x]++;
            } else if (count[x + 1] > 0 && count[x + 2] > 0) {
                count[x + 1]--;
                count[x + 2]--;
                tail[x + 2]++;
            } else {
                return false;
            }
        }

        return true;
    }
};

Python 實作

Counter 對不存在的鍵回傳 0；tail 使用 defaultdict(int)，讓尚未出現的結尾數量也預設為 0。

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        count = Counter(nums)
        tail = defaultdict(int)

        for x in nums:
            if count[x] == 0:
                continue
            count[x] -= 1

            if tail[x - 1] > 0:
                tail[x - 1] -= 1
                tail[x] += 1
            elif count[x + 1] > 0 and count[x + 2] > 0:
                count[x + 1] -= 1
                count[x + 2] -= 1
                tail[x + 2] += 1
            else:
                return False

        return True

正確性說明

演算法始終維持兩個性質：已建立的序列全部合法，而 count 恰好記錄尚未分配的元素。

接著說明每個貪心選擇都不會破壞原本存在的可行解。

可以延長時，優先延長是安全的

假設有一條以 x - 1 結尾的既有序列 A，並且存在一個完成所有分配的合法方案。

若方案已經把目前的 x 接到某條既有序列，就符合演算法的選擇。所有可以接 x 的既有序列都已合法，選擇其中哪條不會影響後續可接的數值。

剩下只需考慮方案沒有延長任何以 x - 1 結尾的既有序列，而是把 x 用來建立新序列 B = [x, x + 1, ...] 的情況。此時 A 在方案中就結束於 x - 1，可以直接把整條 B 接到 A 後面。合併後仍然連續、長度至少為三，使用的元素也完全相同。

因此可以重新安排成一個同樣合法、且先延長既有序列的方案。優先延長不會讓可行解消失。

無法延長時，必須建立新序列

因為依照非遞減順序處理，目前的 x 是尚未分配的最小值。若沒有以 x - 1 結尾的既有序列可以接上它，x 就必須作為新序列的起點。

合法的新序列至少需要 x、x + 1、x + 2。若缺少後兩者之一，就不存在完成分配的方式；若兩者都有，先取這三個值，之後仍可繼續延長。對相同值的不同副本，交換使用位置不影響可行性，因為輸入已排序且序列嚴格遞增。

所以每一步都保留了可行解；若演算法回傳 false，代表必要的分配無法完成。若回傳 true，所有元素都已分配到長度至少為三的連續序列中，符合題意。

複雜度分析

令 n = nums.length。

時間複雜度：平均 $O(n)$。統計一次、走訪一次，每次只進行固定次數的雜湊表操作。這裡採用雜湊表操作平均為 $O(1)$ 的分析。
額外空間複雜度：$O(n)$。兩張表最多記錄與輸入數量成正比的鍵，不需要儲存實際的子序列。若利用本題固定的數值範圍，也可以改用陣列計數。

常見錯誤

優先建立新序列：可能先消耗後續需要的數字；應先嘗試延長既有序列。
新序列只放入一個元素：這份解法仰賴所有既有序列都已合法，建立時必須一次取得三個連續數字。
忘記跳過已使用的值：建立新序列時已提前消耗後面的數字，之後走訪到相同值時，要先檢查 count[x]。
搞錯 tail 的索引：延長時檢查 tail[x - 1]，再將結尾移到 x；建立新序列時增加 tail[x + 2]。最後不需要檢查 tail 是否全為零，它記錄的是已合法序列的結尾數量。
忽略重複元素的數量：每個副本都必須分配，不能只用集合記錄某個數字是否存在。
把子序列當成子陣列：不同序列的元素可以在原陣列中交錯出現。