0163. Missing Ranges¶
题目信息¶
- 题号:
缺失的区间
- 难度:
Easy
- 主题:
数组、区间、顺序扫描
- 原题:
- 重点:
将数值域枚举压缩为相邻已知数之间的最大连续空隙,并安全处理两端边界
题目重述¶
给定闭区间 [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]:
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 段。