ZeroJudge 解題筆記：2996. Smallest Missing Integer Greater Than Sequential Prefix Sum

作者：王一哲
日期：2026年8月11日


LeetCode 題目連結：2996. Smallest Missing Integer Greater Than Sequential Prefix Sum

解題想法

簡單題。我一直覺得我沒有弄清楚題目的意思，但是不小心就過關了，以下是我對題目的解釋。題目給一個索引值為 0 開頭的陣列 $nums$。如果 $nums[0]$ 到 $nums[i]$ 符合條件 $nums[j] = nums[j-1] + 1, ~ 1 \leq j \leq i$，則 $nums[0]$ 到 $nums[i]$ 為連續的 (sequential)。其中的特例為 $nums[0]$，只有 $nums[0]$ 也符合連續的條件。題目要回傳一個最小的整數 $x$，且 $x$ 大於、等於最長連續前綴 (longest sequential prefix)。我的想法是先從 $i = 0$ 開始找最長連續前綴加總 $psum$，接下來將 $nums$ 轉成集合 $num\_set$，用一個 while 迴圈檢查 $psum$ 是否在 $num\_set$ 之中，如果條件成立就將 $psum$ 加 $1$，用線性搜尋的方式找答案。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.22 MB, beats 51.82%.

class Solution:
    def missingInteger(self, nums: List[int]) -> int:
        n, psum = len(nums), nums[0]
        for i in range(1, n):
            if nums[i] == nums[i-1] + 1:
                psum += nums[i]
            else:
                break
        
        num_set = set(nums)
        while psum in num_set:
            psum += 1
        return psum

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 23.01 MB, beats 29.32%.

class Solution {
public:
    int missingInteger(vector<int>& nums) {
        int n = (int)nums.size(), psum = nums[0];
        for(int i = 1; i < n; i++) {
            if (nums[i] == nums[i-1] + 1) {
                psum += nums[i];
            } else {
                break;
            }
        }
        
        set<int> num_set (nums.begin(), nums.end());
        while(num_set.count(psum) == 1) {
            psum++;
        }
        return psum;
    }
};

用 unordered_set 也可以。Runtime: 0 ms, beats 100.00%. Memory: 22.88 MB, beats 64.41%.

class Solution {
public:
    int missingInteger(vector<int>& nums) {
        int n = (int)nums.size(), psum = nums[0];
        for(int i = 1; i < n; i++) {
            if (nums[i] == nums[i-1] + 1) {
                psum += nums[i];
            } else {
                break;
            }
        }
        
        unordered_set<int> num_set (nums.begin(), nums.end());
        while(num_set.count(psum) == 1) {
            psum++;
        }
        return psum;
    }
};