0163. Missing Ranges ==================== 题目信息 -------- :题号: 0163. 缺失的区间 :难度: Easy :主题: 数组、区间、顺序扫描 :原题: `LeetCode 0163 `_ :重点: 将数值域枚举压缩为相邻已知数之间的最大连续空隙,并安全处理两端边界 题目重述 -------- 给定闭区间 ``[lower, upper]``,以及一个严格递增且元素都位于该区间内的整数数组 ``nums``。区间内没有出现在 ``nums`` 中的整数称为缺失整数。 返回按起点升序排列的最短区间列表,使这些闭区间恰好覆盖全部缺失整数:不能覆盖 ``nums`` 中已有的数,也不能遗漏或重复覆盖缺失整数。每个结果项用 ``[start, end]`` 表示,单个缺失数 ``x`` 也表示为 ``[x, x]``。 自建示例 -------- .. code-block:: text 输入:nums = [0,1,3,50,75], lower = 0, upper = 99 输出:[[2,2],[4,49],[51,74],[76,99]] 已知数把目标区间切成四段非空空隙;相邻的缺失数必须合并,才能得到最短列表。 .. code-block:: text 输入:nums = [], lower = -3, upper = -1 输出:[[-3,-1]] 没有任何已知数时,整个目标区间都是一个连续缺失段。 .. code-block:: text 输入:nums = [-1], lower = -1, upper = -1 输出:[] 唯一候选值已经出现,没有缺失区间。 C++ 实现 -------- .. code-block:: cpp #include class Solution { public: std::vector> findMissingRanges( std::vector& nums, int lower, int upper) { std::vector> missing; long long next_missing = lower; for (int value : nums) { if (next_missing < value) { missing.push_back({static_cast(next_missing), value - 1}); } next_missing = static_cast(value) + 1; } if (next_missing <= upper) { missing.push_back( {static_cast(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]``: #. ``next_missing = 0``。遇到 0、1 时都没有空隙,状态依次推进为 1、2; #. 遇到 3,``2 < 3``,输出 ``[2,2]``,再令状态为 4; #. 遇到 50,输出 ``[4,49]``;遇到 75,输出 ``[51,74]``,状态变为 76; #. 扫描结束且 ``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`` 段。