LeetCode 163. 缺失的区间

2022-10-26 HGNULB 约 4 分钟

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

分类

LeetCode CodeTop 简单未解决会员题 1-2 微软

题目描述

✅ 163. 缺失的区间

题意分析

给定闭区间 [lower, upper] 内有序且互不相同的整数，找出其中未出现在数组中的所有连续段。本文采用字符串区间的返回格式：单点返回数字字符串，多点返回 "起点->终点"，对应 Java 的 List<String> 和 Go 的 []string。

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

核心思路

[!blue]
数组已经有序，相邻的两个已出现值 prev、cur 之间没有其他数组元素，因此中间的 [prev + 1, cur - 1] 整段都缺失。只有 cur - prev >= 2 时这段非空；差为 $1$ 时两个值相邻，无需输出。

区间两端也能用同一规则处理：初始令 prev = lower - 1，相当于区间前已有一个虚拟值；处理完数组后，再把 upper + 1 当作最后一个 cur。这两个哨兵只用于计算边界，不会加入输入数组，也不会出现在输出中。

每轮处理完当前缺口后令 prev = cur，继续下一段。所有缺失整数恰好落在某两个相邻已出现值或哨兵之间，因此不会遗漏；不同缺口由已出现值隔开，也不会重叠或需要合并。空数组时，两个哨兵之间直接给出整个闭区间。

lower - 1、upper + 1 以及两者相减都可能超出 $32$ 位整数范围，必须先转换为 $64$ 位再计算。实际输出端点仍是原闭区间内的值，最后按单点或多点格式转成字符串即可。

解题步骤

将 lower 提升为 $64$ 位后减一，作为前置哨兵 prev。

遍历真实元素，最后额外处理尾部哨兵。

cur - prev >= 2 时，把 [prev + 1, cur - 1] 格式化并加入结果。

更新 prev，继续下一段。

返回结果。没有缺失整数时结果为空；只缺少一个整数时，格式化函数返回单个数字字符串。

代码实现

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"

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+1)$，每个元素及尾部哨兵处理一次，整数文本长度有固定上界。

空间复杂度：辅助空间 $O(1)$，输出最多包含 n+1 段。

关键点总结

[!green]

按已有元素之间的缺口推进，无需枚举整个数值范围。

先提升类型再做边界加减。

格式化函数统一处理单点和多点。

易错点总结

[!yellow]

漏掉尾部哨兵：最后一个元素之后的缺失段不会输出。

差为 1 也输出：相邻整数之间没有缺失值。

输出 prev、cur 本身：这两个位置不属于缺口。

Go 用 string 转整数：得到字符编码对应字符，应使用数值格式化函数。

相似题目

题目	难度	关联与区别
228. 汇总区间	简单	原题把已有连续段压成区间，本题找已有数之间以及两端缺失的区间。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/43296374

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！