228. Summary Ranges.md

228. Summary Ranges

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

Thinking:

• Method 1：Set

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> result = new ArrayList<>();
        if(nums == null || nums.length == 0) return result;
        Set<Long> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++)
            set.add((long)nums[i]);
        long start = 0;
        long end = 0;
        for(int i = 0; i < nums.length; i++){
            if(!set.contains((long)nums[i] - 1))
                start = nums[i];
            if(!set.contains((long)nums[i] + 1)){
                end = nums[i];
                if(end == start)
                    result.add(start + "");
                else{
                    result.add(start + "->" + end);
                }
            }
        }
        return result;
    }
}

二刷

1. Only need to traverse the array once but requires O(N) space.

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> list = new LinkedList<>();
        if(nums == null || nums.length == 0) return list;
        String arrow = "->";
        Set<Integer> set = new HashSet<>();
        Integer head = null;
        for(int i = 0; i < nums.length; i++){
            int num = nums[i];
            if(!set.contains(num - 1)){
                if(head != null){
                    if(head != nums[i - 1]){
                        list.add(head + arrow + nums[i - 1]);
                    }else{
                        list.add(head +"");
                    }
                }
                head = num;
            }
            set.add(num);
        }
        if(head != null && nums[nums.length - 1] == head){
            list.add(head + "");
        }else{
            list.add(head + arrow + nums[nums.length - 1]);
        }
        return list;
    }
}