企业官网建设流程全解析

• 教程
• 文档
• 知识库

导读

本文基于 AlgoNote「算法通关手册」的 0163. 缺失的区间 题解文档，系统讲解这道经典数组区间类题目的完整解法。你将掌握：如何用一次线性扫描在有序数组中定位所有缺失区间、如何正确处理单点区间与空数组等边界条件，以及该方法的时间、空间复杂度推导。读完本文，你不仅能独立 AC 此题，还能举一反三地理解区间合并、区间汇总一类题目的通用处理模式。

题目概述

问题描述

给定一个闭区间$[lower, upper]$ 和一个按从小到大排序的整数数组 $nums$，其中所有元素的范围都在闭区间 $[lower, upper]$ 内。如果一个数字 $x$ 位于 $[lower, upper]$ 区间内、但不在 $nums$ 中，则认为 $x$ 是「缺失」的。

要求返回一个准确涵盖所有缺失数字的最小排序区间列表。换句话说：

• $nums$ 的任何元素都不能落在返回的任意区间内；
• 每一个缺失的数字都必须被某个返回区间覆盖；
• 返回的区间列表按升序排列，且区间数量最少。

该题目在 00_05_solutions_list.md 中被归类为「数组」标签、难度「简单」，收录于本书 0100-0199 题解章节。

数据范围与约束

需要注意：数组可以为空（$nums.length = 0$），这是本题一个关键的边界分支。

示例演示

示例 1：区间内有多处空洞。

输入: nums = [0, 1, 3, 50, 75], lower = 0 , upper = 99 输出: [[2,2],[4,49],[51,74],[76,99]] 解释：返回的区间是： [2,2] # 数字 2 缺失，单点区间 [4,49] # 4 到 49 连续缺失 [51,74] # 51 到 74 连续缺失 [76,99] # 75 之后直到上界 99 全部缺失

示例 2：数组恰好覆盖了整个区间，无缺失数字。

输入： nums = [-1], lower = -1, upper = -1 输出： [] 解释： 没有缺失的区间，因为没有缺失的数字。

解题思路：线性扫描

思路 1：线性扫描法

由于 $nums$ 已经按升序排列，且所有元素都在 $[lower, upper]$ 之内，我们可以只遍历数组一次，逐段比较「当前元素」与「前一个已处理边界」之间的空隙，从而拼出所有缺失区间。这本质上是在利用数组的有序性做区间缝隙检测。

具体步骤如下：

1. 初始化边界：设置变量 $prev$ 记录前一个已处理的边界值，初始化为 $lower - 1$。这里取 $lower - 1$ 而非 $lower$，是为了让「第一个元素与区间起点之间的缝隙」也能被统一检测——这是本题最精妙也最容易遗漏的初始化技巧。
2. 遍历数组：对于数组中的每个元素 $nums[i]$，检查它与 $prev$ 之间是否存在缝隙：
   • 若 $prev + 1 < nums[i]$，说明 $(prev, nums[i])$ 之间存在缺失数字，缺失区间为 $[prev + 1, nums[i] - 1]$，将其加入结果；
   • 若 $prev + 1 = nums[i]$，说明区间无缝衔接，没有缺失；
   • （由于 $nums$ 元素互不相同，不会出现 $prev + 1 > nums[i]$ 的情况。）
3. 更新边界：每次处理完一个元素后，令 $prev = nums[i]$。
4. 处理尾部区间：遍历完数组后，还需检查最后一个元素到 $upper$ 之间是否有缺失区间：若 $prev < upper$，则缺失区间为 $[prev + 1, upper]$。

关键点小结：

• 用 $prev$ 记录前一个已处理的边界，每次只与相邻元素比较，无需额外排序；
• 单个数字的缺失同样是一个合法区间，表示为 $[x, x]$；
• 必须处理数组为空的场景：此时 $prev = lower - 1$，若 $lower - 1 < upper$ 则整个 $[lower, upper]$ 都是缺失区间。

思路 1：参考代码

class Solution: def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[List[int]]: result = [] prev = lower - 1 # 前一个边界，初始化为 lower - 1 # 遍历数组中的每个元素 for num in nums: # 如果当前数字与前一个边界之间有间隔，添加缺失区间 if prev + 1 < num: result.append([prev + 1, num - 1]) prev = num # 更新前一个边界 # 检查最后一个数字到 upper 之间是否有缺失区间 if prev < upper: result.append([prev + 1, upper]) return result

思路 1：复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $nums$ 的长度。只需单次线性扫描，每个元素常数时间处理。
• 空间复杂度：$O(1)$（不计返回结果占用的空间），除结果列表外只使用了prev、num等常数额外变量。

边界情况推演

可以看到，prev从lower - 1起步的设计，让头部、中部、尾部三种缝隙被同一套判断逻辑统一覆盖，代码极其简洁。

题目间横向关联

「缺失的区间」属于「数组 + 区间」这一大类题目的典型代表，在 AlgoNote 中它与多道题共享相同的思维框架，建议对照学习：

• 0228. 汇总区间：与本题互为「逆操作」。汇总区间是把数组中连续相邻的元素压缩成区间（"a->b"或"a"）；本题则是找出数组中不存在的连续段。两者都是单次线性扫描即可完成的 $O(n)$ 题，双指针与 $prev$ 边界法的思想一脉相承。
• 0057. 插入区间：处理有序且互不重叠的区间列表，在插入新区间后维持有序性与不重叠性，涉及区间比较与合并逻辑，可作为区间类题目的进阶练习。

从更宏观的角度看，本题是「线性表 + 有序性」的典型应用：数组作为顺序存储的线性表（见 数组基础），其天然的有序性和连续内存特性决定了这类缝隙检测问题可以用 $O(n)$ 扫描而非 $O(n^2)$ 暴力解；而「用两个相邻位置的状态差推导区间」的思想，也与双指针技术（见 双指针）中利用区间单调性压缩复杂度的思路相通。

总结

• 核心结论：对于升序排列且元素互不重复的数组，用 $prev$ 记录前一个边界，线性扫描即可在 $O(n)$ 时间内找出 $[lower, upper]$ 内的全部缺失区间，空间复杂度 $O(1)$。
• 易错点：prev必须初始化为lower - 1；必须额外处理数组尾部到upper的缝隙；不能忘记数组为空的场景（此时整个区间均缺失）。
• 延伸价值：本题的「相邻元素缝隙检测」模式可迁移到区间汇总、区间合并、日程冲突检测等真实场景，是面试中高频出现的思维模型。

如需查阅原始题解文档及更多 LeetCode 题解，可继续浏览 0100-0199 题解索引 与 题目解析总览。

• 教程
• 文档
• 知识库