/ Data Structure and Algorithms  

Leetcode 228. Summary Ranges

Question



Given an array, write consecutive numbers in the form x->y.

Similar Questions

Solution

Traverse the array directly. To determine whether it is continuous or not, it is only necessary to determine whether the current number and the following number are different by 1. When a discontinuity occurs, the current range is saved.

The time complexity is O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static List<String> summaryRanges(int[] nums) {
    if (nums.length == 0) {
        return new ArrayList<>();
    }

    List<String> results = new ArrayList<>();

    int start = nums[0];
    int end;

    for (int i = 0; i < nums.length - 1; i++) {
        // if current + 1 != next number
        if (nums[i] + 1 != nums[i + 1]) {
            end = nums[i];

            if (start != end) {
                results.add(start + "->" + end);
            } else {
                results.add(start + "");
            }

            // next number as start
            start = nums[i + 1];
        }
    }

    // need to consider the last number
    end = nums[nums.length - 1];
    if (start != end) {
        results.add(start + "->" + end);
    } else {
        results.add(start + "");
    }

    return results;
}