[LeetCode] 163. Missing Ranges

You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are in the inclusive range.

A number x is considered missing if x is in the range [lower, upper] and x is not in nums.

Return the smallest sorted list of ranges that cover every missing number exactly. That is, no element of nums is in any of the ranges, and each missing number is in one of the ranges.

Each range [a,b] in the list should be output as:

"a->b" if a != b
"a" if a == b

Example 1:

Input: nums = [0,1,3,50,75], lower = 0, upper = 99
Output: ["2","4->49","51->74","76->99"]
Explanation: The ranges are:
[2,2] --> "2"
[4,49] --> "4->49"
[51,74] --> "51->74"
[76,99] --> "76->99"

Example 2:

Input: nums = [], lower = 1, upper = 1
Output: ["1"]
Explanation: The only missing range is [1,1], which becomes "1".

Example 3:

Input: nums = [], lower = -3, upper = -1
Output: ["-3->-1"]
Explanation: The only missing range is [-3,-1], which becomes "-3->-1".

Example 4:

Input: nums = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing ranges since there are no missing numbers.

Example 5:

Input: nums = [-1], lower = -2, upper = -1
Output: ["-2"]

Constraints:

-109 <= lower <= upper <= 109
0 <= nums.length <= 100
lower <= nums[i] <= upper
All the values of nums are unique.

缺失的区间。

题意是给一个nums数组和一个lower下界，一个upper上界，请你返回在上下界之间的缺失的数字和range。

这个题跟 228题很像，可以一块做。这个题注意题目最后给出的数据范围，是会有溢出的情况的所以一开始就需要把 integer 改成 long 。遍历 nums 的数字，首先第一个数字 num 如果 == lower，那就lower++，不断提高缺失的部分的下界，比如例子中的0和1；当num不等于lower的时候，此时又分两种情况，如果 num == lower + 1 说明只遗漏了一个数字，比如例子中的2，那么就把这一个数字加入结果集；还有一种情况是num很大，则需要返回一个range，[lower, num - 1]。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public List<String> findMissingRanges(int[] nums, int lower, int upper) {
 3         List<String> res = new ArrayList<>();
 4         long alower = (long) lower;
 5         long aupper = (long) upper;
 6         for (int num : nums) {
 7             if (num == alower) {
 8                 alower++;
 9             } else if (alower < num) {
10                 if (alower + 1 == num) {
11                     res.add(String.valueOf(alower));
12                 } else {
13                     res.add(alower + "->" + (num - 1));
14                 }
15                 alower = (long) num + 1;
16             }
17         }
18         if (alower == aupper) {
19             res.add(String.valueOf(alower));
20         } else if (alower < aupper) {
21             res.add(alower + "->" + aupper);
22         }
23         return res;
24     }
25 }