2996.大于等于顺序前缀和的最小缺失整数：模拟（小数据无需哈希表）

【LetMeFly】2996.大于等于顺序前缀和的最小缺失整数：模拟（小数据无需哈希表）

力扣题目链接：https://leetcode.cn/problems/smallest-missing-integer-greater-than-sequential-prefix-sum/

给你一个下标从 0 开始的整数数组 nums 。

如果一个前缀 nums[0..i] 满足对于 1 <= j <= i 的所有元素都有 nums[j] = nums[j - 1] + 1 ，那么我们称这个前缀是一个 顺序前缀 。特殊情况是，只包含 nums[0] 的前缀也是一个 顺序前缀 。

请你返回 nums 中没有出现过的 最小 整数 x ，满足 x 大于等于 最长 顺序前缀的和。

 

示例 1：

输入：nums = [1,2,3,2,5]
输出：6
解释：nums 的最长顺序前缀是 [1,2,3] ，和为 6 ，6 不在数组中，所以 6 是大于等于最长顺序前缀和的最小整数。

示例 2：

输入：nums = [3,4,5,1,12,14,13]
输出：15
解释：nums 的最长顺序前缀是 [3,4,5] ，和为 12 ，12、13 和 14 都在数组中，但 15 不在，所以 15 是大于等于最长顺序前缀和的最小整数。

 

提示：

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 50

解题方法：模拟

使用一个变量$cnt$统计最长前缀的和，初始值$cnt=nums[0]$；接着从$i=1$开始向后遍历，如果$nums[i] \neq nums[i-1]+1$说明前缀终止结束遍历，否则令$cnt$加上$nums[i]$。

当$cnt$在$nums$数组中存在的时候，不断令$cnt+1$，返回第一个不存在于$nums$数组中的$cnt$即为所求。

• 时间复杂度$O(n^2)$，$cnt$每次加一最多加不超过$n$次，每次查找的时间复杂度是$O(n)$。 此小数据量下的$O(n^2)$ 小于 常数很大的$O(n)$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-08-11 09:20:09
 */
class Solution {
public:
    int missingInteger(vector<int>& nums) {
        int cnt = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] != nums[i - 1] + 1) {
                break;
            }
            cnt += nums[i];
        }
        while (ranges::find(nums, cnt) != nums.end()) {  // 注意≠是存在
            cnt++;
        }
        return cnt;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源