228. Summary Ranges

Source link: https://leetcode.com/problems/summary-ranges/

Design

[0,1,2,4,5,7] → [“0->2”,”4->5”,”7”]

  1. Traverse through the array, initialize a variable tmp for storing the current element.
  2. If the next value is contiguous, move the index forward, otherwise stop it.
  3. If the current value equals to tmp, which means there is no other contiguous numbers with it, so simply add tmp into the list. Otherwise, add tmp and the current element into the list.
  4. Return the list.

Implementation

class Solution {
  public List<String> summaryRanges(int[] nums) {
    List<String> res = new ArrayList<>();
    if (nums.length == 1) {
      res.add(nums[0] + "");
      return res;
    }
    for (int i = 0; i < nums.length; i++) {
      int tmp = nums[i];
      while (i != nums.length - 1 && nums[i + 1] - nums[i] == 1) i++;
      if (tmp == nums[i]) {
        res.add(tmp + "");
      } else {
        res.add(tmp + "->" + nums[i]);
      }
    }
    return res;
  }
}

Complexity Analysis

Time: $O(n)$

Space: $O(1)$