题目描述

给定一个排好序的数组 $nums$，所有数都在 $[lower, upper]$ 这个闭区间中，请返回所有缺失的区间。

样例

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

算法

(模拟，数组扫描) $O(n)$

从小到大枚举每个数，枚举过程中维护上一个数的值 $lower$。然后分情况讨论：

1. 当前数等于上一个数，则将 $lower$ 置成当前数；
2. 当前数大于上一个数：
   (1) 只缺失一个数，则直接输出该数；
   (2) 缺失多个数，则输出区间；

时间复杂度分析：整个数据仅扫描一遍，所以时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    vector<string> findMissingRanges(vector<int>& nums, int _lower, int upper) {
        vector<string> res;
        long long lower = _lower;
        for (int i = 0; i < nums.size(); i ++ )
        {
            if (lower < nums[i])
            {
                if (lower == nums[i] - 1) res.push_back(to_string(lower));
                else res.push_back(to_string(lower) + "->" + to_string(nums[i] - 1));
            }
            lower = nums[i] + 1ll;
        }
        if (lower == upper) res.push_back(to_string(lower));
        else if (lower < upper) res.push_back(to_string(lower) + "->" + to_string(upper));
        return res;
    }
};