这个题做了很久。
一开始没审题，以为数组可以是任意数字，测了几个test case感觉答案是错的，才发现lower-upper规定了数组内数字的范围。。这样简单一些。。
我是固定右边，移动左边，进行添加。。
其实不能算做出来，错了无数次，各种edge case完全想不到，改了又改改出个答案来。。
public class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper)
{
List<String> res = new ArrayList<String>();
if(nums.length == 0)
{
add(res,lower,upper);
return res;
}
if(nums.length == 1)
{
if(nums[0] != Integer.MIN_VALUE)
add(res,lower,nums[0]-1);
if(nums[0] != Integer.MAX_VALUE)
add(res,nums[0]+1,upper);
return res;
}
if(lower == upper)
{
for(int i = 0; i < nums.length;i++)
{
if(nums[i] == lower) return res;
else if(nums[i] > lower)
{
add(res,lower,upper);
return res;
}
}
}
else
{
int l = 0;
int r = nums.length-1;
while(l < r)
{
while(l < r && nums[l] < lower) l++;
if(nums[l] != Integer.MIN_VALUE)
add(res,lower,nums[l]-1);
lower = nums[l];
while(l < r && nums[l]+1 == nums[l+1]) l++;
if(l >= r) break;
add(res,nums[l]+1,nums[l+1]-1);
lower = nums[l+1];
}
if(nums[nums.length-1] != Integer.MAX_VALUE)
add(res,nums[nums.length-1]+1,upper);
}
return res;
}
public void add(List<String> res, int a, int b)
{
if(a > b) return;
else if(a == b) res.add("" + a);
else
{
res.add("" + a + "->" + b);
}
}
}
实在是不能忍，重新做了一下，思路没变，代码好看多了。
public class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper)
{
List<String> res = new ArrayList<String>();
if(nums.length == 0)
{
add(res,lower,upper);
return res;
}
for(int i = 0; i < nums.length;)
{
if(nums[i] == lower)
{
i++;
if(i == nums.length) break;
lower++;
}
else
{
add(res,lower,nums[i]-1);
lower = nums[i];
}
}
if(lower != upper)
add(res,lower+1,upper);
return res;
}
public void add(List<String> res, int a, int b)
{
if(a > b) return;
else if(a == b) res.add("" + a);
else
{
res.add("" + a + "->" + b);
}
}
}
选值如果通过 upper - lower = Rindex - Lindex来跳过段数，应该会减少很多时间。。
可惜我不会做。