### 题目

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

Example:

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


### 先用二分查找找到左右界，然后遍历数组

    0               99
|               |
[0, 1, 3, 50, 75]

min lo         hi  max
|/           |  |
[0, 1, 3, 50, 75]


   0
min lo hi max
|   \ | /
[2147483647]


#### 代码

class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> list = new ArrayList<>();
if (lower > upper) return list;
String range = "";
if (nums.length == 0) {
return list;
}
int loIdx = Arrays.binarySearch(nums, lower);
if (loIdx < 0) loIdx = -(loIdx + 1);
int hiIdx = Arrays.binarySearch(nums, upper);
if (hiIdx < 0) hiIdx = -(hiIdx + 1) - 1;
if (loIdx <= hiIdx) {
int leftRange = 0, rightRange = 0;
if (nums[loIdx] != Integer.MIN_VALUE) {
leftRange = lower;
rightRange = nums[loIdx] - 1;
range = toRange(leftRange, rightRange);
}
while (loIdx < hiIdx) {
if (nums[loIdx + 1] != Integer.MIN_VALUE) {
leftRange = nums[loIdx] + 1;
rightRange = nums[loIdx + 1] - 1;
range = toRange(leftRange, rightRange);
}
loIdx++;
}
if (nums[hiIdx] != Integer.MAX_VALUE) {
leftRange = nums[hiIdx] + 1;
rightRange = upper;
range = toRange(leftRange, rightRange);
}
}
return list;
}

private String toRange(int left, int right) {
String range = "";
if (left <= right) {
range = String.valueOf(left);
if (left < right) {
range += "->";
range += String.valueOf(right);
}
}
return range;
}
}


class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> list = new ArrayList<>();
long lo = lower;
for (int i = 0; i < nums.length && nums[i] <= upper; i++) {
long hi = nums[i];
if (hi < lo) continue;
if (hi == lo) {
lo++;
continue;
}
lo = hi + 1;
}
if ((long)upper >= lo) list.add(getRange(lo, upper));
return list;
}

// assertion: for [lo, hi], lo <= hi
private String getRange(long lo, long hi) {
String range = String.valueOf(lo);
if (hi > lo) {
range += "->";
range += String.valueOf(hi);
}
return range;
}
}