【模拟面试问答】深入解析力扣163题：缺失的区间（线性扫描与双指针法详解）

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！

• 推荐：数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
  
• 导航：

• LeetCode解锁1000题: 打怪升级之旅：每题都包括3-5种算法，以及详细的代码实现，刷题面试跳槽必备
• 漫画版算法详解：通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读，看一遍就掌握
• python源码解读：解读python的源代码与调用关系，快速提升代码质量
• python数据分析可视化：企业实战案例：企业级数据分析案例与可视化，提升数据分析思维和可视化能力
• 程序员必备的数学知识与应用：全面详细的介绍了工程师都必备的数学知识

期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️

在本篇文章中，我们将详细解读力扣第163题“缺失的区间”。通过学习本篇文章，读者将掌握如何使用多种方法来解决这一问题，并了解相关的复杂度分析和模拟面试问答。每种方法都将配以详细的解释和ASCII图解，以便于理解。

问题描述

力扣第163题“缺失的区间”描述如下：

给定一个排序的整数数组 nums 和两个整数 lower 和 upper，返回数组中缺失的区间。缺失的区间指的是 nums 中没有出现并且在 [lower, upper] 范围内的整数区间。

示例 1:

输入: nums = [0, 1, 3, 50, 75], lower = 0, upper = 99
输出: ["2", "4->49", "51->74", "76->99"]

示例 2:

输入: nums = [], lower = 1, upper = 1
输出: ["1"]

示例 3:

输入: nums = [], lower = -3, upper = -1
输出: ["-3->-1"]

示例 4:

输入: nums = [-1], lower = -1, upper = -1
输出: []

解题思路

方法一：线性扫描

1. 初步分析：

• 需要找出数组中缺失的区间，并且这些区间要在 [lower, upper] 范围内。
• 可以通过遍历数组，并检查相邻元素之间的差值来确定缺失的区间。

2. 步骤：

• 初始化一个结果列表 result，用于存储缺失的区间。
• 初始化一个变量 prev，表示前一个检查的元素，初始值为 lower - 1。
• 遍历数组nums，对于每个元素num，检查num和prev之间的差值：

• 如果差值等于2，则添加单个缺失的元素到结果列表。
• 如果差值大于2，则添加一个区间到结果列表。
• 更新 prev 为当前元素 num。

• 最后检查 prev 和 upper 之间的差值，处理结束位置的缺失区间。

代码实现

def findMissingRanges(nums, lower, upper):
    result = []
    prev = lower - 1
    for num in nums:
        if num - prev == 2:
            result.append(str(prev + 1))
        elif num - prev > 2:
            result.append(f"{prev + 1}->{num - 1}")
        prev = num
    if upper - prev == 1:
        result.append(str(prev + 1))
    elif upper - prev > 1:
        result.append(f"{prev + 1}->{upper}")
    return result
# 测试案例
print(findMissingRanges([0, 1, 3, 50, 75], 0, 99))  # 输出: ["2", "4->49", "51->74", "76->99"]
print(findMissingRanges([], 1, 1))  # 输出: ["1"]
print(findMissingRanges([], -3, -1))  # 输出: ["-3->-1"]
print(findMissingRanges([-1], -1, -1))  # 输出: []

ASCII图解

假设输入数组为 [0, 1, 3, 50, 75]，lower = 0，upper = 99，图解如下：

初始状态:
nums: [0, 1, 3, 50, 75]
lower: 0, upper: 99
prev: -1
遍历过程:
num = 0, prev = -1, 差值 = 1, 无缺失
num = 1, prev = 0, 差值 = 1, 无缺失
num = 3, prev = 1, 差值 = 2, 缺失单个元素 "2"
num = 50, prev = 3, 差值 = 47, 缺失区间 "4->49"
num = 75, prev = 50, 差值 = 25, 缺失区间 "51->74"
结束检查:
upper = 99, prev = 75, 差值 = 24, 缺失区间 "76->99"
最终结果:
["2", "4->49", "51->74", "76->99"]

方法二：使用双指针法

1. 初步分析：

• 利用双指针的方法来查找数组中缺失的区间。
• 通过两个指针分别遍历数组的不同部分，将结果添加到结果列表中。

2. 步骤：

• 初始化两个指针 left 和 right 分别指向数组的起始和结束。
• 遍历数组，并检查每个指针之间的区间，找到缺失的区间。
• 将缺失的区间添加到结果列表中。

代码实现

def findMissingRanges(nums, lower, upper):
    result = []
    left = lower
    for num in nums:
        if num > left:
            if num - left == 1:
                result.append(str(left))
            else:
                result.append(f"{left}->{num - 1}")
        left = num + 1
    if left <= upper:
        if left == upper:
            result.append(str(left))
        else:
            result.append(f"{left}->{upper}")
    return result
# 测试案例
print(findMissingRanges([0, 1, 3, 50, 75], 0, 99))  # 输出: ["2", "4->49", "51->74", "76->99"]
print(findMissingRanges([], 1, 1))  # 输出: ["1"]
print(findMissingRanges([], -3, -1))  # 输出: ["-3->-1"]
print(findMissingRanges([-1], -1, -1))  # 输出: []

ASCII图解

假设输入数组为 [0, 1, 3, 50, 75]，lower = 0，upper = 99，图解如下：

初始状态:
nums: [0, 1, 3, 50, 75]
lower: 0, upper: 99
left: 0
遍历过程:
num = 0, left = 0, 无缺失
num = 1, left = 1, 无缺失
num = 3, left = 2, 缺失单个元素 "2"
num = 50, left = 4, 缺失区间 "4->49"
num = 75, left = 51, 缺失区间 "51->74"
结束检查:
left = 76, upper = 99, 缺失区间 "76->99"
最终结果:
["2", "4->49", "51->74", "76->99"]

复杂度分析

• 时间复杂度：

• 线性扫描法：O(n)，其中 n 是数组 nums 的长度。遍历数组一次即可完成缺失区间的计算。
• 双指针法：O(n)，其中 n 是数组 nums 的长度。遍历数组一次即可完成缺失区间的计算。

• 空间复杂度：

• 两种方法均为 O(1)，除了存储结果的列表外，只使用了常数空间来存储变量。

模拟面试问答

问题 1：你能描述一下如何解决这个问题的思路吗？

回答：当然。我们需要找到排序数组 nums 中在 [lower, upper] 范围内缺失的区间。通过遍历数组，我们可以检查相邻元素之间的差值，如果差值大于1，则表示存在缺失的区间。我们需要处理数组起始位置和结束位置的特殊情况，以确保所有缺失区间都能被找到。

问题 2：如果数组是空的，你的算法会如何处理？

回答：如果数组是空的，我们只需检查整个 [lower, upper] 范围是否为一个缺失的区间。如果 lower 和 upper 相等，则缺失一个元素。如果 lower 和 upper 不相等，则缺失一个区间。

问题 3：你能解释一下你的代码是如何处理数组起始位置和结束位置的特殊情况的吗？

回答：在代码中，我们首先初始化 prev 为 lower - 1，这样在第一次遍历时可以正确检查起始位置的缺失区间。在遍历结束后，我们检查 prev 和 upper 之间的差值，处理结束位置的缺失区

间。如果 prev 和 upper 之间存在缺失元素或区间，我们将其添加到结果列表中。

总结

本文详细解读了力扣第163题“缺失的区间”，通过线性扫描法和双指针法两种方法，高效地解决了这一问题，并提供了详细的ASCII图解和模拟面试问答。希望读者通过本文的学习，能够在力扣刷题的过程中更加得心应手。

参考资料

• 《算法导论》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
• 力扣官方题解

🌹🌹如果觉得这篇文对你有帮助的话，记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励，非常感谢 ❥(^_-)

❤️❤️关注公众号 数据分析螺丝钉 回复 学习资料 领取高价值免费学习资料❥(^_-)

欢迎关注微信公众号 数据分析螺丝钉