LeetCode 163「缺失的区间」题解：线性扫描法详解（AlgoNote 算法通关手册）

教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文基于 AlgoNote「算法通关手册」的 0163. 缺失的区间 题解文档系统讲解这道经典数组区间类题目的完整解法。你将掌握如何用一次线性扫描在有序数组中定位所有缺失区间、如何正确处理单点区间与空数组等边界条件以及该方法的时间、空间复杂度推导。读完本文你不仅能独立 AC 此题还能举一反三地理解区间合并、区间汇总一类题目的通用处理模式。题目概述问题描述给定一个闭区间$[lower, upper]$ 和一个按从小到大排序的整数数组 $nums$其中所有元素的范围都在闭区间 $[lower, upper]$ 内。如果一个数字 $x$ 位于 $[lower, upper]$ 区间内、但不在 $nums$ 中则认为 $x$ 是「缺失」的。要求返回一个准确涵盖所有缺失数字的最小排序区间列表。换句话说$nums$ 的任何元素都不能落在返回的任意区间内每一个缺失的数字都必须被某个返回区间覆盖返回的区间列表按升序排列且区间数量最少。该题目在 00_05_solutions_list.md 中被归类为「数组」标签、难度「简单」收录于本书 0100-0199 题解章节。数据范围与约束约束项取值范围边界值$-10^{9} \le lower \le upper \le 10^{9}$数组长度$0 \le nums.length \le 10^{3}$元素范围$lower \le nums[i] \le upper$元素性质$nums$ 中的所有值互不相同且数组已按升序排序需要注意数组可以为空$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]$ 之内我们可以只遍历数组一次逐段比较「当前元素」与「前一个已处理边界」之间的空隙从而拼出所有缺失区间。这本质上是在利用数组的有序性做区间缝隙检测。具体步骤如下初始化边界设置变量 $prev$ 记录前一个已处理的边界值初始化为 $lower - 1$。这里取 $lower - 1$ 而非 $lower$是为了让「第一个元素与区间起点之间的缝隙」也能被统一检测——这是本题最精妙也最容易遗漏的初始化技巧。遍历数组对于数组中的每个元素 $nums[i]$检查它与 $prev$ 之间是否存在缝隙若 $prev 1 nums[i]$说明 $(prev, nums[i])$ 之间存在缺失数字缺失区间为 $[prev 1, nums[i] - 1]$将其加入结果若 $prev 1 nums[i]$说明区间无缝衔接没有缺失由于 $nums$ 元素互不相同不会出现 $prev 1 nums[i]$ 的情况。更新边界每次处理完一个元素后令 $prev nums[i]$。处理尾部区间遍历完数组后还需检查最后一个元素到 $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 初值执行过程结果数组为空如lower0, upper99$-1$跳过循环-1 99[[0,99]]整个区间缺失单个元素恰好等于上下界如nums[-1], lower-1, upper-1$-2$循环内无缝隙prev-1不小于upper-1[]无缺失缺失全在头部如nums[5,6], lower0, upper6$-1$首元素前检测到[0,4][[0,4]]缺失全在尾部如nums[0,1], lower0, upper5$-1$循环无缝隙尾部检测[2,5][[2,5]]可以看到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 题解索引 与 题目解析总览。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote 算法通关手册LeetCode 0164「最大间距」线性时间解法详解基数排序实战AlgoNote 算法通关手册LeetCode 0164「最大间距」线性时间解法详解基数排序实战 本篇技术指南以 AlgoNote https://lin教程文档知识库LeetCode 163 Missing Ranges 缺失区间问题详解leetcode 仓库中的单次扫描实现指南LeetCode 163 Missing Ranges 缺失区间问题详解leetcode 仓库中的单次扫描实现指南 导读 本文围绕 LeetCode 163「示例工程教程AlgoNote 算法通关手册LeetCode 0066「加一」数组模拟加法题解AlgoNote 算法通关手册LeetCode 0066「加一」数组模拟加法题解 本篇技术指南以「算法通关手册」AlgoNote仓库中 LeetCode教程文档知识库上一篇Sup为邮件达人打造的命令行邮箱客户端下一篇AutoTrain Advanced自监督学习表示评估线性分类器与下游任务性能终极指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考