Given a sorted integer array where the range of elements are in the inclusive range [lower, upper], return its missing ranges.

For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].

 

---

题目标签：Array

　　题目给了我们一个nums array， lower 和 upper， 让我们遍历完nums 之后找到 从lower 到 upper 中缺失的区间。 首先设立一个 long start = lower；每一次遍历一个数字，都把start 更新为这个数字的下一个数字。如果当前的数字，比 start 大的话，那么说明遇到了缺失的区间，这里有可能只有一个数字缺失，也有可能至少两个数字缺失。当最后遍历完了nums， 还要检查一下start 是否等于 upper， 如果等于的话，说明 最后一个数字， upper 是缺失的； 如果start 小于 upper， 说明至少2个数字缺失。

我们来看一下例子：

[0, 1, 3, 50, 75]， lower = 0， upper = 99；

start = 0;

遍历开始

0  1  3  50  75　　当前数字 0 > start 0 ? 没有。 更新 start = 0 + 1，继续遍历；

0  1  3  50  75　　当前数字 1 > start 1 ? 没有。 更新 start = 1 + 1，继续遍历；

0  1  3  50  75　　当前数字 3 > start 2 ? 是的，说明有missing 的情况，这里只缺失一个数字，加入 res = ["2"]，更新 start = 3 + 1，继续遍历；

0  1  3  50  75　　当前数字 50 > start 4 ? 是的，说明有missing 的情况， 这里缺失至少2个数字， 加入 res = ["2", "4->49"]，更新 start = 50 + 1，继续遍历；

0  1  3  50  75　　当前数字 75 > start 51 ? 是的，说明有missing 的情况， 这里缺失至少2个数字，加入 res = ["2", "4->49", "51->74"]， 更新 start = 75 + 1，遍历结束；

最后还要检查一下 start 76 == upper 还是 start 76 < upper， 这里小于，所以至少2个数字缺失， 加入 res = ["2", "4->49", "51->74", "76->99"]

 

注意的是，当 nums 里出现 2147483647 的时候，要注意 overflow。

 

Java Solution:

Runtime beats 14.29% 

完成日期：09/01/2017

关键词：Array

关键点：一直更新start 并且 检测缺失的是一个数字或者多个数字

 

1 class Solution  2 { 3     public List
     
       findMissingRanges(int[] nums, int lower, int upper)  4     { 5         List
      
        res = new ArrayList<>(); 6          7         long start = lower; 8          9         for(int i=0; i
       
         start) // meaning there is some range missing here12             {13                 if(start == nums[i] - 1) // if only one number is missing14                     res.add("" + start);15                 else if(start < nums[i] - 1) // if more than one number is missing16                     res.add("" + start + "->" + (nums[i] - 1) );17             }18             19             start = (long)nums[i] + (long)1; // update the start from current + 1 number for next round    20         }21         22         // check last possible missing range23         if(start == upper) // meaning the previous one is upper - 1, so the upper is missing one here24             res.add("" + start);25         else if(start < upper)    // meaning at least two numbers are missing26             res.add("" + start + "->" + upper);27             28             29         return res;30     }31 }
       
      
     

参考资料：N/A

 

LeetCode 算法题目列表 -