Description
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"]
Solution
题目看似不难，但是有坑，很容易会overflow。考虑下面这个test case:
[2147483647]
-2147483648
2147483647
还有这个：
[-2147483648,-2147483648,0,2147483647,2147483647]
-2147483648
2147483647
感觉不用long的话，很难避免overflow。
还需要注意的是，nums虽然是sorted，但可能有重复元素哦。
Iteration, time O(n), space O(1)
class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
long need = lower; // use long to avoid overflow
List<String> missingRanges = new ArrayList<>();
for (int num : nums) {
if (need < num) {
missingRanges.add(getRange((int) need, num - 1));
}
need = 1l + num; // don't overflow here!
}
if (need <= upper) {
missingRanges.add(getRange((int) need, upper));
}
return missingRanges;
}
public String getRange(int n1, int n2) {
return (n1 == n2) ? String.valueOf(n1)
: String.format("%d->%d", n1, n2); // elegant
}
}
