228. Summary Ranges

https://leetcode.com/problems/summary-ranges/description/

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"]
Explanation: 0,1,2 form a continuous range; 4,5 form a continuous range.

Example 2:

Input:  [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: 2,3,4 form a continuous range; 8,9 form a continuous range.

Thoughts

双指针指向当前范围，相连就让右边的指针一直往前直到i == len(nums) - 1 or num != nums[i + 1] - 1。

Code

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        res, beg = [], None
        for i, num in enumerate(nums):
            if beg is None: beg = num
            if i == len(nums) - 1 or num != nums[i + 1] - 1:
                if num == beg:
                    res.append(str(num))
                else:
                    res.append(str(beg) + '->' + str(num))
                beg = None
        return res
        

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

        return res;
    }
}

Analysis

时间复杂度O(N).