2026-11-16:找到所有数组中消失的数字Ⅱ。用go语言,给定一个整数序列 nums,并给出闭区间端点 lower 和 upper。把闭区间 [lower, upper] 内所有没有在 nums 中出现过的整数看作空缺值。要求找出这些空缺值组成的连续段,每一段用起点和终点表示,形成形如 [start, end] 的结果。所有连续空缺应合并为一段,结果按起点从小到大排列;如果该区间内没有空缺值,则返回空数组。

1 <= nums.length <= 100000。

1 <= nums[i] <= 100000。

1 <= lower <= upper <= 100000。

输入: nums = [3,9,7], lower = 1, upper = 12。

输出: [[1,2],[4,6],[8,8],[10,12]]。

解释:

缺失整数为 [1, 2, 4, 5, 6, 8, 10, 11, 12]。

将这些缺失整数合并成最少数量的连续区间后,得到 [1, 2]、[4, 6]、[8, 8] 和 [10, 12]。

因此,答案为 [[1, 2], [4, 6], [8, 8], [10, 12]]。

题目来自力扣4031。

大体步骤如下:

  1. 1. 加入边界哨兵
    代码先把lower-1和upper+1追加到nums中。
    这样做的目的是保证即使[lower, upper]的开头或结尾存在空缺,也能通过相邻元素差被发现。
    例如输入nums = [3,9,7]、lower = 1、upper = 12,加入后得到[3,9,7,0,13]。

  2. 2. 对数组排序
    使用slices.Sort(nums)将数组升序排序。
    排序后,数组中相邻元素之间的“空隙”就对应可能缺失的整数段。
    上述例子排序后为[0,3,7,9,13]。

  3. 3. 二分查找扫描范围左端点
    l := sort.SearchInts(nums, lower+1)找的是排序数组中第一个大于等于lower+1的位置。
    这个位置之前的相邻差主要涉及lower之前的数,不需要生成结果;从l开始检查,可以覆盖lower附近可能缺失的区间。
    例子中lower+1 = 2,排序数组中第一个大于等于 2 的元素是 3,所以l = 1。

  4. 4. 二分查找扫描范围右端点
    r := sort.SearchInts(nums, upper)找的是排序数组中第一个大于等于upper的位置。
    循环会扫描到r,用于处理upper之前以及上边界附近的空缺。由于前面加入了upper+1哨兵,所以即使upper本身缺失,也能在扫描到upper+1时生成以upper结尾的空缺段。
    例子中upper = 12,排序数组中第一个大于等于 12 的元素是 13,所以r = 4。

  5. 5. 扫描相邻元素,寻找连续空缺段
    循环从i = l到i <= r,每次比较nums[i]和nums[i-1]。
    如果nums[i] - nums[i-1] > 1,说明这两个相邻的已出现整数之间至少隔了一个整数,因此中间部分全部没有出现在nums中,形成一段连续空缺:
    起点是nums[i-1] + 1,终点是nums[i] - 1。
    如果差值等于 1,说明两个数连续,没有空缺;如果差值为 0,说明有重复元素,也没有空缺。对例子[0,3,7,9,13]:

  • • 比较 3 和 0,差为 3,大于 1,空缺为[1,2];

  • • 比较 7 和 3,差为 4,大于 1,空缺为[4,6];

  • • 比较 9 和 7,差为 2,大于 1,空缺为[8,8];

  • • 比较 13 和 9,差为 4,大于 1,空缺为[10,12]。

6. 收集结果
每发现一个间隔大于 1 的相邻对,就把对应的[起点, 终点]加入答案数组ans。
因为数组已经升序排序,并且扫描方向是从左到右,所以生成的空缺区间天然按起点从小到大排列,不需要再额外排序。
最终得到[[1,2],[4,6],[8,8],[10,12]]。

7. 返回答案
扫描结束后直接返回ans。如果[lower, upper]内没有缺失整数,那么扫描过程中不会产生任何区间,返回空数组。

复杂度分析:

设原始nums的长度为n。加入两个哨兵后长度最多为n+2,仍为O(n)。

  • • 时间复杂度:
    排序需要O(n log n);两次二分查找各需要O(log n);扫描相邻元素最多O(n)。因此总时间复杂度为O(n log n),排序是主要开销。

  • • 额外空间复杂度:
    append可能导致新的底层数组分配,最坏需要O(n)额外空间;排序本身是原地排序,但递归栈等辅助空间为O(log n);答案ans在最坏情况下可能包含O(n)个区间。因此总额外空间复杂度为O(n)。如果不把返回结果本身计入辅助空间,则最坏也主要受append扩容影响,为O(n)。

Go完整代码如下:

package main

import (
"fmt"
"slices"
"sort"
)

func findDisappearedNumbers(nums []int, lower, upper int) (ans [][]int) {
nums = append(nums, lower-1, upper+1)
slices.Sort(nums)

l := sort.SearchInts(nums, lower+1)
r := sort.SearchInts(nums, upper)

for i := l; i <= r; i++ {
if nums[i]-nums[i-1] > 1 {
ans = append(ans, []int{nums[i-1] + 1, nums[i] - 1})
}
}
return
}

func main() {
nums := []int{3, 9, 7}
lower := 1
upper := 12

result := findDisappearedNumbers(nums, lower, upper)
fmt.Println(result)
}
打开网易新闻 查看精彩图片

Python完整代码如下:

# -*-coding:utf-8-*-

from bisect import bisect_left
from typing import List

def find_disappeared_numbers(nums: List[int], lower: int, upper: int) -> List[List[int]]:
arr = sorted(nums + [lower - 1, upper + 1])

l = bisect_left(arr, lower + 1)
r = bisect_left(arr, upper)

ans: List[List[int]] = []
for i in range(l, r + 1):
if arr[i] - arr[i - 1] > 1:
ans.append([arr[i - 1] + 1, arr[i] - 1])

return ans

def main():
nums = [3, 9, 7]
lower = 1
upper = 12

result = find_disappeared_numbers(nums, lower, upper)
print(result)

if __name__ == "__main__":
main()
打开网易新闻 查看精彩图片

C++完整代码如下:

  





std::vector int >> findDisappearedNumbers(std::vector< int > nums, int lower, int upper) {
nums.push_back(lower - 1 );
nums.push_back(upper + 1 );
std::sort(nums.begin(), nums.end());

int l = std::lower_bound(nums.begin(), nums.end(), lower + 1 ) - nums.begin();
int r = std::lower_bound(nums.begin(), nums.end(), upper) - nums.begin();

std::vector int >> ans;
for ( int i = l; i <= r; ++i) {
if (nums[i] - nums[i - 1 ] > 1 ) {
ans.push_back({nums[i - 1 ] + 1 , nums[i] - 1 });
}
}
return ans;
}

int main() {
std::vector< int > nums = { 3 , 9 , 7 };
int lower = 1 , upper = 12 ;

auto result = findDisappearedNumbers(nums, lower, upper);

std::cout << "[" ;
for (size_t i = 0 ; i < result.size(); ++i) {
std::cout << "[" << result[i][ 0 ] << " " << result[i][ 1 ] << "]" ;
if (i + 1 < result.size()) std::cout << " " ;
}
std::cout << "]" << std::endl;

return 0 ;
}
打开网易新闻 查看精彩图片

芯谷ai:xinguhub.com/sign-up?aff=txk5

我们相信人工智能为普通人提供了一种“增强工具”,并致力于分享全方位的AI知识。在这里,您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”,发消息可获得面试资料,让AI助力您的未来发展。