自己的做法
算法思想
定义一个begin变量，表示每一段区间的开始索引。一次访问数组每个元素，如果该元素 + 1不等于 下一个元素，表示应开始一段新区间。首先将begin到当前元素插入到区间数组中，然后begin置为下个元素的索引，继续遍历。
需要注意的是数组的末尾边界。因为要比较当前元素和下一个元素的值，所以当 访问到最后一个元素时，没有下一个元素，这时候应直接插入区间数组。
算法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
static vector<string> summaryRanges(vector<int>& nums) {
vector<string> ranges;
int begin = 0;
for(int i = 0; i < nums.size(); i++) {
if(i == 0) {
begin = nums[0];
}
if(i == nums.size() - 1 || nums[i] + 1 != nums[i + 1]) {
ranges.push_back(begin == nums[i] ?
to_string(begin) : to_string(begin) + "->" + to_string(nums[i]));
if(i != nums.size() - 1) {
begin = nums[i + 1];
}
}
}
return ranges;
}
};
|
性能分析
时间复杂度：遍历了一遍数组，O(n)。
空间复杂度：除了用于输出的区间数组，剩下只有一个begin变量，O(1)。
官方解法和我这个基本思想一样。