LeetCode 163 Missing Ranges

思路

题目中的lower和upper都不会出现在给定数组的内部，只会在两端出现。
首先将lower与数组第0个元素进行合并，然后再依次向后合并下去，最后将最后一个元素与upper再合并。合并：写一个addRange函数进行合并操作。
【注意：有可能会出现int溢出的现象，所以这里有2种方法处理：一个是将addRange的输入参数从int转成long；另一种是在调用addRange之前判断是否可以在addRange中+1或-1，从而避免溢出】

复杂度

时间复杂度O(n), 空间复杂度O(n)

代码

处理溢出方式1——转为long：

class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
    List<String> ans = new ArrayList<>();if(nums == null || nums.length == 0) {
    addRange(ans, lower, upper);return ans;}addRange(ans, lower, (long)nums[0]-1);for(int i = 1; i < nums.length; i++) {
    addRange(ans, (long)nums[i-1]+1, (long)nums[i]-1);}addRange(ans, (long)nums[nums.length-1]+1, upper);return ans;}public void addRange(List<String> ans, long start, long end) {
    if(start > end)return;if(start == end) {
    ans.add(start + "");} else {
    ans.add(start + "->" + end);}}
}

处理溢出方式2——提前判断:

class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
    List<String> ans = new ArrayList<>();if(nums == null || nums.length == 0) {
    addRange(ans, lower, upper);return ans;}if(nums[0] > Integer.MIN_VALUE)addRange(ans, lower, nums[0]-1);for(int i = 1; i < nums.length; i++) {
    if(nums[i-1] < Integer.MAX_VALUE && nums[i] > Integer.MIN_VALUE)addRange(ans, nums[i-1]+1, nums[i]-1);}if(nums[nums.length-1] < Integer.MAX_VALUE)addRange(ans, nums[nums.length-1]+1, upper);return ans;}public void addRange(List<String> ans, int start, int end) {
    if(start > end)return;if(start == end) {
    ans.add(start + "");} else {
    ans.add(start + "->" + end);}}
}