2996. Smallest Missing Integer Greater Than Sequential Prefix Sum

題目 / Problem

中文： 給你一個下標從 0 開始的整數陣列 nums。

如果前綴 nums[0..i] 滿足：對所有 1 <= j <= i 都有 nums[j] = nums[j-1] + 1，那麼這個前綴就是「連續的（sequential）」。特別地，只有 nums[0] 一個元素的前綴也算連續。

請找出最長的連續前綴，計算它的總和 s。然後回傳「大於或等於 s、且不在 nums 裡」的最小整數 x。

English: You are given a 0-indexed integer array nums.

A prefix nums[0..i] is sequential if every element is exactly one more than the previous one (nums[j] = nums[j-1] + 1 for all 1 <= j <= i). A single-element prefix [nums[0]] counts as sequential.

Find the longest sequential prefix, take its sum s, then return the smallest integer x that is >= s and is not present in nums.

Constraints / 限制： - 1 <= nums.length <= 50 - 1 <= nums[i] <= 50

Worked example / 範例： nums = [1,2,3,2,5] → the longest sequential prefix is [1,2,3] (since nums[3]=2 ≠ 3+1), sum = 6. Is 6 in the array? No. So the answer is 6.

名詞解釋 / Glossary

• 前綴 / prefix： 陣列從最左邊開始、連續的一段元素，例如 nums[0..i]。A contiguous chunk of the array starting at index 0.
• 連續前綴 / sequential prefix： 每個元素都比前一個大剛好 1 的前綴，如 [3,4,5]。A prefix where each value is exactly one greater than the one before it.
• 前綴和 / prefix sum： 把前綴裡所有元素加起來的總和。The sum of all elements in that prefix.
• 雜湊集合 / hash set： 一種可以在近乎 O(1) 時間內判斷「某個數在不在集合裡」的資料結構。A data structure that lets you check "is this value present?" in roughly constant time. C++ 用 unordered_set；在 C 裡因為數值範圍很小（1~50），我們可以用一個布林陣列來模擬。
• 布林標記陣列 / boolean marker array： 用一個陣列 seen[v] 記錄「值 v 是否出現過」，適合當數值範圍很小時。An array where seen[v] = true means value v appeared; ideal when the range of possible values is small.
• 原地掃描 / single pass： 只從頭到尾走一遍陣列就完成計算。Compute the answer by walking through the array once.

思路

最直接的想法分成兩步。第一步找最長連續前綴：從下標 1 開始往右看，只要 nums[i] == nums[i-1] + 1 就繼續延伸，一旦某個位置不滿足，前綴就在這裡斷掉，我們停下來。過程中把經過的元素累加得到總和 s。因為前綴一定是從 0 開始的一整段，所以第一次斷裂的位置就決定了最長連續前綴——不需要考慮後面的元素。第二步是找答案：我們要的是「大於等於 s、又不在陣列裡」的最小整數。最笨的辦法是從 s 開始，s、s+1、s+2……每次都去掃一遍整個陣列看在不在，直到找到一個不在的為止。這樣最壞是 O(n²) 級別，但因為 n 只有 50、數值也只到 50，其實完全跑得動。不過我們可以更漂亮：先把陣列所有值丟進一個集合（或小布林陣列），之後每次判斷「在不在」就是 O(1)。從 s 開始遞增，第一個不在集合裡的數就是答案。注意 s 最大約 50 個數相加，但因為每個連續前綴其實是遞增序列，總和不會太大，答案也一定存在（總能找到一個沒出現的數）。

The natural approach has two phases. First, find the longest sequential prefix: start from index 1 and keep extending as long as nums[i] == nums[i-1] + 1; the moment this fails, the prefix ends and we stop, accumulating the sum s along the way. Since the prefix must start at index 0 as one unbroken run, the first break point fully determines the longest prefix — we never look past it. Second, find the answer: the smallest integer >= s that is missing from the array. The brute-force version scans the whole array for each candidate starting at s, which is O(n²)-ish but perfectly fine for n ≤ 50. The cleaner version first dumps every value into a set (or a tiny boolean array, since values are only 1–50), giving O(1) membership checks. Then we count up from s and return the first value not in the set. An answer always exists because there are infinitely many integers but only finitely many array values, so eventually we hit one that's missing.

逐步走查 / Walkthrough

Example: nums = [1,2,3,2,5]

Phase 1 — find longest sequential prefix & its sum / 找最長連續前綴與總和：

So the longest sequential prefix is [1,2,3] and s = 6. / 最長連續前綴是 [1,2,3]，總和 s = 6。

Phase 2 — smallest missing integer >= s / 找大於等於 s 的最小缺失整數：

Values present in nums / 陣列中出現的值：{1, 2, 3, 5}.

6 is not in {1,2,3,5}, so the answer is 6. / 6 不在集合中，答案是 6。

Solution — C

// 演算法 / Algorithm:
// 1) 從左到右找「最長連續前綴」，同時累加它的總和 s。
//    Walk left-to-right to find the longest sequential prefix and sum it into s.
// 2) 用一個布林陣列標記所有出現過的值，再從 s 往上找第一個沒出現的數。
//    Mark every value seen in a boolean array, then scan up from s for the first missing one.

int missingInteger(int* nums, int numsSize) {
    // s 先設成第一個元素，因為長度至少為 1，單元素前綴一定連續。
    // Start s at the first element; length >= 1, so a single-element prefix is always sequential.
    int s = nums[0];

    // 從下標 1 開始檢查是否能繼續延伸連續前綴。
    // From index 1, check whether the sequential run can keep extending.
    for (int i = 1; i < numsSize; i++) {
        // 只有當這個數剛好是前一個數 +1 時，前綴才連續。
        // The prefix stays sequential only if this value is exactly previous + 1.
        if (nums[i] == nums[i - 1] + 1) {
            s += nums[i];   // 把這個元素加進總和 / add this element to the sum
        } else {
            break;          // 一旦斷裂就停止，前綴到此為止 / break: the prefix ends here
        }
    }

    // seen[v] = 1 代表值 v 在 nums 裡出現過。值域 1..50，開 51 大小即可安全索引。
    // seen[v] = 1 means value v appears in nums. Values are 1..50, so size 51 covers all indices.
    int seen[51] = {0};   // 全部初始化為 0（都沒出現） / initialise all to 0 (nothing seen yet)

    // 把每個元素標記成「出現過」。
    // Mark each element as "present".
    for (int i = 0; i < numsSize; i++) {
        seen[nums[i]] = 1;   // 用值當索引直接打標記 / use the value itself as the index
    }

    // 從 s 開始往上找第一個沒被標記的整數。
    // Starting at s, find the first integer that is not marked as seen.
    int x = s;
    // 條件：x 在 1..50 範圍內 且 已經出現過，就繼續往上找。
    // While x is within 1..50 AND already seen, keep incrementing.
    // 超過 50 的數一定沒在陣列裡（值最大 50），可以直接回傳。
    // Any x above 50 cannot be in the array (max value is 50), so it must be the answer.
    while (x <= 50 && seen[x] == 1) {
        x++;   // 這個數在陣列裡，試下一個 / this value exists, try the next one
    }

    return x;   // 第一個大於等於 s 且缺失的整數 / first integer >= s that is missing
}

Solution — C++

// 演算法 / Algorithm:
// 1) 一次掃描找出最長連續前綴的總和 s（相鄰相差 1 才延伸）。
//    One pass to sum the longest sequential prefix (extend only when neighbours differ by 1).
// 2) 把所有值放進 unordered_set，從 s 往上找第一個不在集合裡的整數。
//    Put all values in an unordered_set, then scan up from s for the first missing integer.

#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int missingInteger(vector<int>& nums) {
        // s 從第一個元素起算；陣列非空，單元素前綴必為連續。
        // Start s at nums[0]; the array is non-empty and a single element is always sequential.
        int s = nums[0];

        // 從下標 1 開始嘗試延長連續前綴。
        // From index 1, try to extend the sequential prefix.
        for (int i = 1; i < (int)nums.size(); i++) {
            if (nums[i] == nums[i - 1] + 1)   // 剛好比前一個大 1 才算連續 / exactly one greater
                s += nums[i];                 // 累加進總和 / add to the sum
            else
                break;                        // 斷裂就停止 / stop at the first break
        }

        // unordered_set：雜湊集合，可用 count() 在近乎 O(1) 時間判斷值是否存在。
        // unordered_set: a hash set giving near-O(1) membership checks via count().
        // 用範圍 for 迴圈把每個值插入集合（begin..end 逐一走訪）。
        // Range-for loop inserts every value (iterates each element in turn).
        unordered_set<int> seen(nums.begin(), nums.end());

        // 從 s 開始遞增，直到找到一個不在集合裡的整數。
        // Increment from s until we hit an integer that is not in the set.
        int x = s;
        // count(x) 回傳 x 在集合裡的個數（0 或 1）；為 1 表示存在，需繼續往上找。
        // count(x) returns how many times x is in the set (0 or 1); 1 means present, so keep going.
        while (seen.count(x)) {
            x++;   // 這個數已存在，換下一個 / this value exists, move to the next
        }

        return x;   // 大於等於 s 的最小缺失整數 / smallest missing integer >= s
    }
};

複雜度 / Complexity

• Time: O(n) — 第一次掃描找連續前綴走過至多 n 個元素；建立集合／標記陣列也是一次 O(n) 掃描；最後從 s 往上找答案，因為值域只有 1~50，最多再走約 50 步（常數）。整體由陣列長度 n 主導，所以是線性。The prefix scan and set-building are each one pass over the n elements; the final upward search runs at most ~50 steps (a constant, since values are ≤ 50). Everything is dominated by n, hence linear.
• Space: O(n)（C++）／O(1)（C）— C++ 的 unordered_set 最多存 n 個值。C 版用固定大小 51 的布林陣列，與輸入大小無關，所以是常數空間。The C++ unordered_set holds up to n values. The C version uses a fixed size-51 boolean array independent of input size, so constant space.

Pitfalls & Edge Cases

• 單元素陣列 / single-element array： 例如 nums = [1]。連續前綴就是 [1]，s = 1；因為 1 已出現，答案是 2。程式碼中 s 預設成 nums[0]、迴圈從 i = 1 開始，天然處理了這種情況。The loop starting at i = 1 naturally handles length-1 input.
• 忘記單元素前綴也算連續 / forgetting the single-element prefix counts： 若把 s 初始化成 0 再依賴迴圈相加，第一個元素會漏掉。務必先把 nums[0] 算進去。Initialising s to nums[0] (not 0) avoids dropping the first element.
• 答案可能超出值域 / answer may exceed the value range： 若陣列剛好塞滿了 s, s+1, ..., 50，答案會是 51。C 版用 x <= 50 && seen[x] 的條件，一旦 x > 50 就跳出並回傳（超過 50 的數保證缺失）。C++ 版用集合則不受此限。The C loop guards with x <= 50; the C++ set version has no such bound.
• 只看第一次斷裂 / only the first break matters： 後面即使又出現一段連續數字（如 [3,4,5,1,12,14,13] 裡的 12,13,14），也不是前綴，不能算進 s。用 break 確保我們在第一次不連續時就停手。Using break ensures later runs are ignored — they aren't prefixes.
• 陣列索引越界 / array index safety： C 版 seen 開大小 51（下標 0~50），因為值最大 50。若只開 50 會在 seen[50] 越界。Size 51 keeps seen[50] in bounds.
• 不需要擔心 overflow / no overflow risk： 最多 50 個數、每個最多 50，總和上限遠低於 int 範圍，所以 int 足夠。With ≤ 50 values each ≤ 50, int is more than enough.