0163. Missing Ranges

题目信息

题号:
  1. 缺失的区间

难度:

Easy

主题:

数组、区间、顺序扫描

原题:

LeetCode 0163

重点:

将数值域枚举压缩为相邻已知数之间的最大连续空隙,并安全处理两端边界

题目重述

给定闭区间 [lower, upper],以及一个严格递增且元素都位于该区间内的整数数组 nums。区间内没有出现在 nums 中的整数称为缺失整数。

返回按起点升序排列的最短区间列表,使这些闭区间恰好覆盖全部缺失整数:不能覆盖 nums 中已有的数,也不能遗漏或重复覆盖缺失整数。每个结果项用 [start, end] 表示,单个缺失数 x 也表示为 [x, x]。

自建示例

输入:nums = [0,1,3,50,75], lower = 0, upper = 99
输出:[[2,2],[4,49],[51,74],[76,99]]

已知数把目标区间切成四段非空空隙;相邻的缺失数必须合并,才能得到最短列表。
输入:nums = [], lower = -3, upper = -1
输出:[[-3,-1]]

没有任何已知数时,整个目标区间都是一个连续缺失段。
输入:nums = [-1], lower = -1, upper = -1
输出:[]

唯一候选值已经出现,没有缺失区间。

C++ 实现

#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> findMissingRanges(
        std::vector<int>& nums, int lower, int upper) {
        std::vector<std::vector<int>> missing;
        long long next_missing = lower;

        for (int value : nums) {
            if (next_missing < value) {
                missing.push_back({static_cast<int>(next_missing), value - 1});
            }
            next_missing = static_cast<long long>(value) + 1;
        }

        if (next_missing <= upper) {
            missing.push_back(
                {static_cast<int>(next_missing), upper});
        }
        return missing;
    }
};

题解

原始搜索空间为什么不合适

最直接的想法是在 lower 到 upper 之间逐个枚举整数,判断它是否出现在 nums 中,再把连续缺失值合并。这样确实严格遵循定义,但工作量取决于数值区间宽度 upper - lower + 1,而不是输入数组长度。即使 nums 只有几个数,宽阔区间也会 产生大量“这个值仍然缺失”的重复判断。

题目已经给出更强的信息:nums 严格递增。已知数之间不可能再藏着别的已知数, 因此缺失答案只可能出现在三类位置:第一个已知数之前、相邻已知数之间、最后一个已知数 之后。无需访问缺失区间里的每个值,只要确定每段空隙的两个端点。

把已覆盖前缀压缩成一个状态

令 next_missing 表示“当前尚未被处理的最小整数”。初始为 lower。扫描到已知数 value 时:

  • 若 next_missing < value,那么从 next_missing 到 value - 1 没有任何 已知数,整段都是缺失区间;

  • 若 next_missing == value,当前最小候选恰好已存在,没有空隙需要输出;

  • 处理完 value 后,将状态推进到 value + 1。

由于输入严格递增且都在目标区间内,不会出现 next_missing > value 的有效扫描状态。 循环结束后,若 next_missing <= upper,尾部尚未处理的部分整体构成最后一个缺失区间。

这个状态把“从上一个已知数之后到哪里为止”所需的历史压缩为一个整数,不需要额外集合, 也不需要给数组插入哨兵。

最短列表为何自然得到

每次输出的 [next_missing, value - 1] 左侧紧邻区间边界或前一个已知数,右侧紧邻 当前已知数,因此它已经是一个不能继续扩展的最大连续缺失段。不同输出之间至少隔着一个 nums 中的已知数,无法合并;而一段内部若再拆开,只会增加区间数量。

所以扫描既不会漏掉缺失数,也不会覆盖已知数,并且恰好为每个最大连续缺失段输出一次, 由此得到题目要求的最短列表。

具体走读

对 nums = [0,1,3,50,75]、[lower,upper] = [0,99]:

  1. next_missing = 0。遇到 0、1 时都没有空隙,状态依次推进为 1、2;

  2. 遇到 3,2 < 3,输出 [2,2],再令状态为 4;

  3. 遇到 50,输出 [4,49];遇到 75,输出 [51,74],状态变为 76;

  4. 扫描结束且 76 <= 99,补上尾部 [76,99]。

若 nums 为空,循环不执行,初始的 next_missing = lower 会让整个 [lower,upper] 作为尾部空隙输出。若数组已经覆盖目标区间内的每个整数,状态最终为 upper + 1,尾部条件失败,答案为空。

溢出边界

若 value 恰为 32 位最大整数,直接用 int 计算 value + 1 会溢出。 next_missing 使用 long long,并在加法前提升 value,让“已处理到上界之后” 仍是一个可表示的状态。写入答案的端点一定处于原始 int 区间内,因此再转回 int 是安全的。

复杂度

设 nums 长度为 n,每个已知数只处理一次,时间复杂度为 O(n);除返回结果外 只维护 next_missing,额外空间复杂度为 O(1)。答案本身最多包含 n + 1 段。