大于等于序列前缀和的最小缺失整数

题目描述

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

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

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

先别急着写代码，把题目看懂

这题考察的其实不是算法有多难，而是你读题读得够不够细。很多同学一上来就懵，觉得这不就是个"找缺失整数"吗？其实坑藏在"前缀"和"最长"这两个词里。

坑一：什么是"顺序前缀"？——必须从下标 0 开始

先看一个具体例子，比如输入：

ums = [3, 4, 5, 1, 12, 14, 13]

很多人第一反应是：哎，12, 13, 14 不也是连续的（每个都比前一个大 1）吗？怎么最长顺序前缀不是它们？

这里就是最容易踩的坑！

“前缀”（prefix）的定义，是从 nums[0] 开始、连续的一段。 前缀永远要从数组的第一个元素 nums[0] 出发：

• nums[0..0] = [3]
• nums[0..1] = [3, 4]
• nums[0..2] = [3, 4, 5]
• nums[0..3] = [3, 4, 5, 1]

而 12, 13, 14 虽然在数组里彼此连续，但它们不是从 nums[0] 开始的，所以它们根本不叫"前缀"，直接被排除掉。

再配合"顺序"这个限定（每个元素比前一个大 1）：

• [3]：只有一个元素，是顺序前缀 ✅
• [3, 4]：4 = 3 + 1，是顺序前缀 ✅
• [3, 4, 5]：5 = 4 + 1，是顺序前缀 ✅
• [3, 4, 5, 1]：1 != 5 + 1，不是顺序前缀 ❌

所以最长顺序前缀就是 [3, 4, 5]，和为：

$$3 + 4 + 5 = 12$$

坑二：“大于等于"和"缺失"怎么理解？

题目要的是"最小整数 x，满足 x >= 12，并且 x 没有在 nums 里出现过”。

那我们从 12 开始一个一个往后找，看谁"不在数组里"：

• 12 在数组里（nums[4]），不符合"缺失" ❌
• 13 在数组里（nums[6]），不符合 ❌
• 14 在数组里（nums[5]），不符合 ❌
• 15 不在数组里，而且 15 >= 12 ✅

所以答案是 15。

💡 看出来了吗？最后那串 12, 13, 14 虽然进不了"前缀"，但它们却挡在答案的路上——因为它们在数组里存在，所以从 12 到 14 全被跳过，直到 15 才"漏"出来。这也是这题有意思的地方。

解决方法

理清了题意，代码就水到渠成了，分两步：

1. 找出最长顺序前缀并求和

顺序前缀一定从 nums[0] 开始，所以我们从下标 0 往后走，只要下一个元素等于当前元素加 1，就继续累加；一旦断掉（下一个不等于当前 + 1），立刻停止。这样找出来的就是"最长的顺序前缀"。

int sum = nums[0];                      // 至少包含 nums[0]
for (int i = 1; i < n; i++) {
    if (nums[i] == nums[i - 1] + 1) {   // 是顺序的，继续累加
        sum += nums[i];
    } else {
        break;                          // 断掉了，最长顺序前缀到此为止
    }
}

注意：这个循环只要发现第一次"断掉"就 break，不会回头去看后面的元素。这正是保证了我们取到的是前缀（从 nums[0] 开始的一段），而不是数组里随便哪一段连续子序列。

2. 从 sum 开始找第一个缺失的整数

先把整个数组装进一个 unordered_set，方便快速判断"某个数在不在数组里"。然后从 sum 开始，只要当前数在集合里（说明它出现过、不是"缺失"），就 +1 继续找；直到找到第一个不在集合里的数，它就是答案。

unordered_set<int> s(nums.begin(), nums.end());  // 快速判断某个数是否存在
int x = sum;
while (s.count(x)) {   // 只要 x 出现过，就继续找下一个
    x++;
}
return x;

完整代码

#include <vector>
#include <unordered_set>

using namespace std;

class Solution {
public:
    int missingInteger(vector<int>& nums) {
        int n = nums.size();

        // 特殊情况：空数组直接返回 1（没有前缀可求和，最小的缺失整数就是 1）
        if (n == 0) return 1;

        // ========== 第一步：找最长顺序前缀并求和 ==========
        // 顺序前缀从 nums[0] 开始，一旦断掉立即停止
        int sum = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] == nums[i - 1] + 1) {
                sum += nums[i];
            } else {
                break;
            }
        }

        // ========== 第二步：从 sum 开始找第一个缺失的整数 ==========
        unordered_set<int> s(nums.begin(), nums.end());
        int x = sum;
        while (s.count(x)) {   // x 出现过就继续 +1
            x++;
        }
        return x;
    }
};