【C++刷题】力扣-#163-缺失的区间

题目描述

给定一个整数数组 nums 和两个整数 lower 和 upper，找出数组中在范围 [lower, upper] 内缺失的所有整数，包括边界。

示例

示例 1:

输入: nums = [0,1,3,50,75], lower = 0, upper = 99
输出: ["2","4","5","6","7","8","9","10",…,"49","51","52",…,"74","76",…,"99"]
解释: 范围 [0,99] 内缺失的整数是 [2,3,4,5,6,7,8,9,10,…,49,51,52,…,74,76,…,99]。

示例 2:

输入: nums = [0,1,2,3,4], lower = 0, upper = 4
输出: []
解释: 数组中没有缺失的数字。

示例 3:

输入: nums = [0,1,3,50,75], lower = 0, upper = 0
输出: []
解释: lower 等于 upper 时，没有缺失数字。

题解

这个问题可以通过遍历给定的范围并检查每个数字是否存在于数组中来解决。

1. 初始化：创建一个空列表 result 来存储缺失的数字。
2. 遍历范围：从 lower 到 upper 遍历，检查每个数字是否存在于数组 nums 中。
   ○ 对于每个数字 i，在数组 nums 中查找是否存在。
   ○ 如果不存在，则将 i 添加到 result 列表中。
3. 返回结果：返回 result 列表。

代码实现

vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
    vector<string> result;
    for (int i = lower; i <= upper; ++i) {
        if ((i == lower || find(nums.begin(), nums.end(), i - 1) == nums.end()) && find(nums.begin(), nums.end(), i) == nums.end()) {
                result.push_back(to_string(i));
        }
    }
    return result;
}

复杂度分析

● 时间复杂度：O(n * (upper - lower + 1))，其中 n 是数组 nums 的长度。对于范围内的每个数字，我们可能需要遍历整个数组来查找它是否存在。
● 空间复杂度：O((upper - lower + 1))，因为我们需要存储缺失的数字。
这个算法的优势在于它直接模拟了查找缺失数字的过程。