问题描述
问题编号为 163，题目要求我们在给定的闭区间 [lower, upper] 内，找出那些在整数数组 nums 中缺失的数字区间。这就好比我们有一个完整的数字区间，但其中部分数字被拿走了，我们需要找出那些空缺的部分。
解题思路与过程剖析
方法签名
1 | public List> findMissingRanges(int[] nums, int lower, int upper) |
这个方法接收三个参数：一个整数数组 nums，以及两个整数 lower 和 upper，它的任务是返回一个包含所有缺失区间的列表。每个缺失区间都由一个包含两个整数的列表表示，分别是区间的起始和结束值。
初始化操作
1 2 | List> res = new ArrayList();long pre = (long) lower - 1; |
这里，我们创建了一个 res 列表，用于存储最终的结果。而 pre 变量被初始化为 lower - 1，它的作用是记录前一个检查过的数字，方便我们后续判断是否存在缺失区间。使用 long 类型是为了避免可能出现的整数溢出问题。
数组遍历
1 | for (int i = 0; i |
我们通过一个 for 循环来遍历数组 nums。需要注意的是，循环条件是 i ，这意味着我们会多进行一次迭代。在最后一次迭代时，cur 会被设为 upper + 1，这样做是为了确保我们能检查到区间 [lower, upper] 的最后一个数字。
检查缺失区间
1 2 3 4 5 6 | if (cur - pre > 1) { List list = new ArrayList(); list.add((int) pre + 1); list.add((int) cur - 1); res.add(list);} |
在每次迭代中，我们会比较 cur 和 pre 的差值。如果差值大于 1，说明在 pre 和 cur 之间存在缺失的数字，我们就创建一个新的区间，起始值为 pre + 1，结束值为 cur - 1，并将这个区间添加到结果列表 res 中。
更新 pre
1 | pre = cur; |
为了确保下一次检查的准确性，我们将 pre 更新为当前的 cur，这样在下次迭代时，我们就能基于新的 pre 值继续判断是否存在缺失区间。
返回结果
1 | return res; |
最后，我们返回包含所有缺失区间的列表 res，这就是我们整个算法的最终输出。
完整代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Solution{ publicList>findMissingRanges(int[] nums,int lower,int upper){ List> res =newArrayList(); long pre =(long) lower -1; for(int i =0; i 1){ List list =newArrayList(); list.add((int) pre +1); list.add((int) cur -1); res.add(list); } pre = cur; } return res; }} |
复杂度分析
时间复杂度
虽然原内容中时间复杂度标记为 O(∗)，但实际上，我们只对数组 nums 进行了一次遍历，因此时间复杂度为 O(n)O(n)，其中 nn 是数组 nums 的长度。
空间复杂度
空间复杂度方面，除了存储结果的列表 res 外，我们只使用了常数级的额外空间，所以空间复杂度为 O(m)O(m)，这里的 mm 是缺失区间的数量。
通过以上的分析，我们可以看到，这个算法巧妙地利用了一次遍历和简单的条件判断，高效地解决了缺失区间的查找问题。希望大家在遇到类似的算法问题时，也能像“东百牧码人”一样，通过清晰的思路和简洁的代码来攻克难题。
以上就是Java缺失区间的查找方法的详细内容，更多关于Java查找缺失区间的资料请关注IT俱乐部其它相关文章！
