[LeetCode]228. Summary Ranges

Problem

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

1
2
3
4
5
6
7
8
9
10
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.

Solution

Analysis

范围归纳.如果数组中数字是连续的,那么归入一个范围,设置起点和终点;如果只有一个数字时,独自构成一个范围, 添加到结果数组中.

Code

注意大数, int范围问题. INT_MAX + 1, 导致的错误.

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
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
vector<string> result;
if (nums.empty()) return result;

int size = nums.size();
for (int i=0; i< size; i++){
// 相当于双指针,start指向开始, next指向下一个元素
long start = nums[i], next = (long)nums[i]+1;

int j = i+1;
while (j < size && nums[j] == next){
j++;
next++;
}
next--;// 有效的数字范围

if (next == start) result.push_back(to_string(start));
else result.push_back(to_string(start) + "->" + to_string(next));

if (j >= size) break;
else i = j-1;// 指针更新.

}

return result;
}
};
您的支持就是我更新的最大动力!谢谢!