LeetCode 163. 缺失的区间

2022-10-26 HGNULB 约 9 分钟

文章信息 6 个分类 1 个标签

分类

题目描述

✅ 163. 缺失的区间

题意分析

给定一个升序排列且元素互不相同的整数数组 nums，以及一个闭区间 [lower, upper]。要找出这个闭区间里所有没有出现在 nums 中的数，把它们按连续段聚合成若干个区间，按顺序返回。

输出有固定格式：段内只有一个数时输出这个数本身（如 "2"），有多个数时输出 "起点->终点"（如 "4->49"）。格式化是独立于算法的一步，要单独抽出来处理。

「已排序且无重复」是关键前提。它保证了缺失段只可能出现在三个地方：第一个元素左侧、相邻两元素之间、最后一个元素右侧。如果没有这个前提，就得先排序去重。

数组元素以及 lower、upper 都可能取到 32 位整型的极值。这是本题最隐蔽的陷阱：算法天然需要用到 lower - 1 和 upper + 1 这样的哨兵，而 lower 可能就是 Integer.MIN_VALUE、upper 可能就是 Integer.MAX_VALUE，直接加减会溢出翻转。

边界情况相当多：nums 为空时整个 [lower, upper] 都是缺失的；nums 恰好铺满整个区间时结果为空列表；lower 等于 upper 且该数不在 nums 中时输出单个数。

元素保证落在 [lower, upper] 范围内，所以不需要过滤越界的输入值。

解法：扫一遍构造缺失区间

核心思路

最朴素的想法是从 lower 数到 upper，逐个判断是否在 nums 里，再把连续的缺失数合并成段。这在逻辑上正确，但 upper - lower 可以接近 $2^{32}$，逐个枚举完全不可行。

瓶颈在于按「数值」推进，而真正决定答案的只有 nums 里那几个数的位置——它们把值域切成了若干段，段与段之间的空隙就是答案。

于是换成按「元素」推进：只要知道相邻两个已出现的数 prev 和 cur，中间缺失的就是 [prev + 1, cur - 1]，这段非空的条件是 cur - prev >= 2。整个问题变成扫一遍数组，对每个相邻对做一次这样的判断。

麻烦的是首尾两段：第一个元素左边的空隙是 [lower, nums[0] - 1]，最后一个元素右边的空隙是 [nums[n-1] + 1, upper]。它们的形式与中间段不同，单独写两段代码既冗长又容易出错。

消除这种不对称的标准手法是加哨兵：把 prev 初始化为 lower - 1，并在遍历到数组末尾之后额外处理一个虚拟的 cur = upper + 1。这样首段就变成「虚拟元素 lower - 1 与 nums[0] 之间的空隙」，尾段变成「nums[n-1] 与虚拟元素 upper + 1 之间的空隙」，与中间段的公式完全一致，一个循环全部搞定。

哨兵带来的代价是可能越界，所以 prev 和 cur 必须用 64 位存储。用 long 之后，lower - 1 即使在 lower 为 Integer.MIN_VALUE 时也能正确表示成 $-2^{31} - 1$，不会翻转成正数。

不变量是：每轮循环开始时，prev 是「上一个已被覆盖的数」（首轮为虚拟的 lower - 1），且 [lower, prev] 范围内所有缺失段都已被写入结果。循环体处理 (prev, cur) 这个开区间的空隙后把 prev 更新为 cur，不变量继续成立。循环跑完 n + 1 轮后，整个 [lower, upper] 被完整覆盖。

每个缺失整数都恰好落在一对相邻真实元素或哨兵之间，因此会被输出一次；每个输出区间又严格位于两个已出现值之间，所以其中没有误收已有元素。由此得到不漏、不重的完整答案。

解题步骤

把 prev 初始化为 (long) lower - 1。这个虚拟元素让「第一个真实元素之前的缺失段」自动落进通用公式，省掉一整段特判。必须先转 long 再减一，否则 lower 为最小值时会先溢出。

循环下标 i 从 0 走到 nums.length（含），一共 n + 1 轮。多出的那一轮专门用来引入尾部哨兵。

每轮确定 cur：i 落在数组内就取 nums[i]，i 等于数组长度就取 (long) upper + 1。同样先转 long 再加一，防止 upper 为最大值时翻转成负数。

判断 cur - prev >= 2 是否成立。这个条件等价于「prev 与 cur 之间至少隔着一个整数」——差为 1 表示两者相邻、无空隙，差为 0 或负数在本题的有序无重复前提下不会出现。

条件成立时把区间 [prev + 1, cur - 1] 格式化后加入结果。左右端点各偏移 1，因为 prev 和 cur 本身都是已被覆盖的数，不属于缺失部分。

格式化单独抽成一个函数：两端相等就只输出一个数，否则输出 "a->b"。把格式与算法分离，能让主循环的下标逻辑保持干净。

每轮末尾把 prev 更新为 cur，推进到下一段。更新必须在判断之后，否则空隙会被算成 0 长度。

循环结束直接返回结果列表。不需要额外补尾，因为尾部哨兵那一轮已经处理过了。

以 nums = [0, 1, 3, 50, 75]、lower = 0、upper = 99 走一遍：prev 初始化为 -1。i = 0 时 cur = 0，差为 1，无空隙，prev 变 0。i = 1 时 cur = 1，差为 1，无空隙，prev 变 1。i = 2 时 cur = 3，差为 2 满足条件，输出区间 [2, 2]，两端相等故格式化为 "2"，prev 变 3。i = 3 时 cur = 50，差为 47，输出 [4, 49] 即 "4->49"，prev 变 50。i = 4 时 cur = 75，差为 25，输出 [51, 74] 即 "51->74"，prev 变 75。i = 5 时已越过数组末尾，取尾哨兵 cur = 100，差为 25，输出 [76, 99] 即 "76->99"。最终结果是 ["2", "4->49", "51->74", "76->99"]。再看极值用例 nums = [-2147483648, 2147483647]、lower = -2147483648、upper = 2147483647：prev 为 $-2^{31} - 1$，i = 0 时 cur 为 $-2^{31}$，差为 1 无空隙；i = 1 时 cur 为 $2^{31} - 1$，差极大，输出 "-2147483647->2147483646"；i = 2 时尾哨兵为 $2^{31}$，差为 1 无空隙。若 prev 用 int 存，第一步就会翻转成 $2^{31} - 1$，差变成负数，整个结果全错。

代码实现

import java.util.ArrayList;
import java.util.List;

// 用 long 处理 lower-1 与 upper+1 的哨兵，避免溢出。
class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> res = new ArrayList<>();
        long prev = (long) lower - 1;

        for (int i = 0; i <= nums.length; i++) {
            long cur;
            if (i == nums.length) {
                cur = (long) upper + 1;
            } else {
                cur = nums[i];
            }
            if (cur - prev >= 2) {
                res.add(format(prev + 1, cur - 1));
            }
            prev = cur;
        }

        return res;
    }

    private String format(long a, long b) {
        if (a == b) {
            return String.valueOf(a);
        }
        return a + "->" + b;
    }
}

import "strconv"

// 用 int64 处理 lower-1 与 upper+1 的哨兵，避免溢出。
func findMissingRanges(nums []int, lower int, upper int) []string {
	res := []string{}
	prev := int64(lower) - 1

	for i := 0; i <= len(nums); i++ {
		cur := int64(upper) + 1
		if i < len(nums) {
			cur = int64(nums[i])
		}
		if cur-prev >= 2 {
			res = append(res, formatRange(prev+1, cur-1))
		}
		prev = cur
	}

	return res
}

func formatRange(a int64, b int64) string {
	if a == b {
		return strconv.FormatInt(a, 10)
	}
	return strconv.FormatInt(a, 10) + "->" + strconv.FormatInt(b, 10)
}

复杂度分析

时间复杂度：$O(n)$。数组只扫一遍，多出的那一轮用于处理尾部哨兵；每轮做一次比较、至多一次常数长度的字符串拼接。与值域跨度无关，这正是它优于逐数枚举的地方。

空间复杂度：$O(1)$（不计输出）。只维护 prev、cur 两个标量；结果列表的规模由缺失段数决定，最多 $n + 1$ 段，属于必要输出而非额外开销。

关键点总结

值域跨度巨大而关键点稀疏时，一定要按「元素」推进而不是按「数值」推进——前者是 $O(n)$，后者是 $O(upper - lower)$，在 32 位值域下差了九个数量级。

首尾两段与中间段形式不同，是这类扫描题的通病。加虚拟哨兵（前置 lower - 1、后置 upper + 1）能把三种情况统一成一个公式，代码量和出错面同时下降。

哨兵一旦要在边界上做加减，就必须换用更宽的类型。lower 为 Integer.MIN_VALUE、upper 为 Integer.MAX_VALUE 是必考用例，用 long 是最省事的防御。

「两数之间有空隙」的判据是差值不小于 2，而不是差值大于 0。差为 1 表示相邻、空隙为空，这个偏移是所有区间缺失题的共同判据。

输出格式化要与算法解耦。把「单点还是区间」的分支封进独立函数，主循环就只需关心下标推进，两部分互不干扰。

面试视角：这题代码短，考的是边界的完备性。上手前主动列出四个必测用例——空数组、nums 铺满整个区间、lower == upper、极值溢出——再讲哨兵统一三种情形，最后写代码，这个顺序最能体现工程素养。常见追问是「如果 nums 未排序或有重复呢」，答案是先排序去重再走同样流程，复杂度升到 $O(n \log n)$。

易错点总结

错误写法：prev 用 int 存并写成 lower - 1。用例 nums = [-2147483648, 2147483647]、lower = -2147483648、upper = 2147483647 → prev 溢出翻转成 $2^{31} - 1$，差值变负，返回空列表，正确答案是 ["-2147483647->2147483646"]。

错误写法：尾哨兵用 int 存并写成 upper + 1。用例 nums = [0]、lower = 0、upper = 2147483647 → 哨兵翻转成 $-2^{31}$，尾段被判为无空隙，漏掉 "1->2147483647"。

错误写法：循环写成 i < nums.length，不额外走尾哨兵那一轮。用例 nums = [0, 1, 3, 50, 75]、lower = 0、upper = 99 → 结果缺少末尾的 "76->99"。

错误写法：判据写成 cur - prev > 0 或 cur > prev。用例 nums = [0, 1]、lower = 0、upper = 1 → 相邻的 0 和 1 之间被认为有空隙，输出 [1, 0] 这种起点大于终点的非法区间，正确答案是空列表。

错误写法：区间端点忘记偏移，直接输出 [prev, cur]。用例 nums = [0, 3]、lower = 0、upper = 3 → 输出 "0->3"，把已存在的 0 和 3 也算成缺失，正确答案是 "1->2"。

错误写法：单点区间仍按 "a->b" 格式输出。用例 nums = [0, 1, 3]、lower = 0、upper = 3 → 输出 "2->2"，正确答案是 "2"。

错误写法：prev 的更新写在判断之前。用例 nums = [0, 3]、lower = 0、upper = 3 → prev 提前变成 cur，差值恒为 0，永远检测不到空隙，返回空列表。

错误写法：不加前置哨兵，改为对 i == 0 单独特判但忘了 nums 为空的情形。用例 nums = []、lower = 1、upper = 1 → 循环一次都不执行，返回空列表，正确答案是 ["1"]。

错误写法：从 lower 逐个数到 upper 判断是否缺失。用例 lower = -2147483648、upper = 2147483647 → 需要遍历约 43 亿个数，直接超时。

错误写法：Go 用 string(a) 转换整数端点。用例 nums = []、lower = 65、upper = 65 → string(65) 得到字符 "A" 而不是文本 "65"，应使用 strconv.FormatInt。

相似题目

题目	难度	考察点
228. 汇总区间	简单	反过来聚合已出现的连续段，输出格式与本题完全一致
56. 合并区间	中等	输入本身就是区间，需先排序再按重叠关系合并
57. 插入区间	中等	在有序区间列表中插入一段并合并，考的是三段式扫描的边界处理
1288. 删除被覆盖区间	中等	排序规则要对起点升序、终点降序，判据从空隙换成包含关系
253. 会议室 II	中等	关注区间重叠的最大层数，需要把端点拆开排序或用堆维护
268. 丢失的数字	简单	同为「找缺失」，但保证只缺一个，可用求和或异或做到 $O(1)$ 空间
41. 缺失的第一个正数	困难	无序且需原地哈希，找的是第一个缺失的正整数而非全部缺失段