163.Missing-Ranges.md

163. Missing Ranges

---

题目地址

https://leetcode.com/problems/missing-ranges/

题目描述

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

代码

Approach #1

Time: O(N) && Space: O(1)

class Solution {
  public List<String> findMissingRanges(int[] nums, int lower, int upper) {
		List<String> res = new ArrayList<String>();
    int next = lower;
    
    for (int i = 0; i < nums.length; i++) {
      if (nums[i] < next) {
        	continue;
      }	 
      else if (nums[i] == next) {
        next++;
      }
      else { // nums[i] > next
        res.add(getRange(next, nums[i] - 1));
      	next = nums[i] + 1;
      }
    }
    
    if (next <= upper) {
      res.add(getRange(next, upper));
    }
    
    return res;
  }
  
  String getRange(int n1, int n2) {
    reutrn (n1 == n2) ? String.valueOf(n1) : String.format("%d->%d", n1, n2);
  }
}