E2996.大于等于顺序前缀和的最小缺失整数

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

这个问题可以通过简单的遍历和集合（Set）查找来解决。

解题思路

1. 寻找最长顺序前缀： 从数组的第一个元素 nums[0] 开始，检查后续元素是否满足 nums[j] == nums[j - 1] + 1。一旦不满足或者到达数组末尾，就停止。
2. 计算和： 将这个最长顺序前缀的所有元素相加，得到初始和 s。
3. 寻找缺失的最小整数： 为了提高查找效率，先将原数组 nums 存入一个集合（Set）中。 从 s 开始，判断 s 是否在集合中：
   • 如果在，说明 s 已存在，执行 s = s + 1 继续检查。
   • 如果不在，当前的 s 即为满足条件的最小缺失整数。

Python 代码实现

from typing import List

class Solution:
    def missingInteger(self, nums: List[int]) -> int:
        # 1. 寻找最长顺序前缀的和
        # 初始前缀至少包含第一个元素
        prefix_sum = nums[0]
        for i in range(1, len(nums)):
            # 检查是否连续递增
            if nums[i] == nums[i - 1] + 1:
                prefix_sum += nums[i]
            else:
                # 一旦不连续，直接跳出循环
                break
        
        # 2. 将数组存入集合，方便 O(1) 复杂度查找
        num_set = set(nums)
        
        # 3. 从 prefix_sum 开始，寻找第一个不在数组中的整数
        curr = prefix_sum
        while curr in num_set:
            curr += 1
            
        return curr

复杂度分析

• 时间复杂度：$O(n)$。
  • 遍历前缀最坏情况需要 $O(n)$。
  • 将数组转为集合需要 $O(n)$。
  • 虽然 while 循环会增加 curr，但由于数组长度最大为 50，且 nums[i] 最大为 50，查找次数非常有限（最坏情况下也不会超过数组长度的量级）。
• 空间复杂度：$O(n)$。
  • 主要开销是存储数组元素的集合 num_set。