Missing Ranges

Description

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"].

Hint

Train of Thought

要判断边界, 同时还要考虑数据溢出问题. e.g [1,1,1] 1, 1 return [] [2147483647],0,2147483647 return ["0 -> 2147483646"] [], 1, 1, return 1 [-1] -1, 0, return 0

以lower作为活动的指针

Code

public class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> res = new ArrayList<String>();

        if (nums == null || nums.length == 0) {//[], 1, 1, return 1
            res.add(getStr(lower, upper));
            return res;
        }


        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == lower) {
                lower++;
                continue;
            } else if (lower < nums[i]){//[1,1,1] 1, 1 return []
                res.add(getStr(lower, nums[i] - 1));
                if(nums[i] == upper) {
                    return res;
                }
                lower = nums[i] + 1;//[2147483647],0,2147483647
            } 
        }

        if (lower <= upper) {//[-1] -1, 0
            res.add(getStr(lower, upper));
        }

        return res;
    }

    private String getStr(int i, int j) {
        if (i == j) {
            return String.valueOf(i);
        } else {
            return String.valueOf(i) + "->" + String.valueOf(j);
        }
    }

Complexity