[LeetCode 163] Missing Ranges (m

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

思路和 # 228 Summary Ranges类似，但区别在于这题有重复，需要注意去重。和开头、结尾数字的处理

Time: O (n)
Space: O(1)

class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> result = new ArrayList<> ();
        if (nums == null || nums.length == 0) {
            String temp = "";
            if (lower != upper) {
                temp = lower + "->" + upper;
            } else {
                temp = String.valueOf (lower);
            }
             
            result.add (temp);
            return result;
        }
        
        if (lower == upper) {
            return result;
        }

        
        if (nums[0] > lower) {
            String entry = (nums[0] - 1 == lower) ? String.valueOf (lower) : lower + "->" + (nums[0] - 1);
            result.add (entry);
        }
        
        
        for (int i = 1; i < nums.length; i++) {
            // 注意去重！！！！！
            if (nums[i - 1] == nums[i] || nums[i - 1] + 1 == nums[i])
                continue;
            
            String entry = nums[i - 1] + 1 == nums[i] - 1 ? String.valueOf (nums[i - 1] + 1) : (nums[i - 1] + 1) + "->" + (nums[i] - 1);
            result.add (entry);
        }
        
        // 注意最后一个的处理
        int lastNumber = nums[nums.length - 1];
        if (lastNumber < upper) {
            String entry = "";
            if (lastNumber + 1 == upper) {
                entry = String.valueOf (upper);
            } else {
                entry = (lastNumber + 1) + "->" + upper;
            }
            result.add (entry);
        }
          
        return result;
    }
}