日期: 2026年8月11日

目标

给你一个下标从 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

思路

定义数组 nums 的顺序前缀是满足 1 <= j <= i, nums[j] = nums[j - 1] + 1 的前缀，返回大于等于数组顺序前缀和且没有出现在数组的最小整数。

使用哈希表保存数组所有元素，计算顺序前缀和 sum，从 sum 返回第一个不在哈希表中的整数即可。

代码

/**
 * @date 2026-08-11 8:58
 */
public class MissingInteger2996 {

    public int missingInteger(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0] + 1;
        }
        Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toSet());
        int sum = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] != nums[i - 1] + 1) {
                break;
            }
            sum += nums[i];
        }
        while (set.contains(sum)) {
            sum++;
        }
        return sum;
    }
}

性能