Google
228 Summary Ranges

1. Question

Given a sorted integer array without duplicates, return the summary of its ranges.
Example 1:
1
Input: [0,1,2,4,5,7]
2
3
Output: ["0->2","4->5","7"]
Copied!
Example 2:
1
Input: [0,2,3,4,6,8,9]
2
3
Output: ["0","2->4","6","8->9"]
Copied!

2. Implementation

(1) Scan Line
1
class Solution {
2
public List<String> summaryRanges(int[] nums) {
3
List<String> res = new ArrayList<>();
4
5
for (int i = 0; i < nums.length; i++) {
6
int curNum = nums[i];
7
8
while (i < nums.length - 1 && (nums[i + 1] - nums[i] == 1)) {
9
++i;
10
}
11
12
if (curNum != nums[i]) {
13
res.add(curNum + "->" + nums[i]);
14
}
15
else {
16
res.add(nums[i] + "");
17
}
18
}
19
return res;
20
}
21
}
Copied!

3. Time & Space Complexity

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