228 Summary Ranges

228. Summary Ranges

1. Question

Given a sorted integer array without duplicates, return the summary of its ranges.

Example 1:

Input: [0,1,2,4,5,7]

Output: ["0->2","4->5","7"]

Example 2:

Input: [0,2,3,4,6,8,9]

Output: ["0","2->4","6","8->9"]

2. Implementation

(1) Scan Line

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            int curNum = nums[i];

            while (i < nums.length - 1 && (nums[i + 1] - nums[i] == 1)) {
                ++i;
            }

            if (curNum != nums[i]) {
                res.add(curNum + "->" + nums[i]);
            }
            else {
                res.add(nums[i] + "");
            }
        }
        return res;
    }
}

3. Time & Space Complexity

Scan Line: 时间复杂度O(n), 空间复杂度O(n)