博文中会简要介绍Leetcode P0228题目分析及解题思路。
“Summary Ranges”是一道比较简答的题目，只需要模拟一遍题目要求就可以得到结果。
You are given a sorted unique integer array nums.
Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.
Each range [a,b] in the list should be output as:
- “a->b” if a != b
- “a” if a == b
这道题的解法的思路比较简洁明了。我们维护一个left指针和一个right指针，每次移动right直到发现当前的right指向的元素不等于前一个元素加上1，此时说明递增序列中断，则可以生成一个连续区间，然后将right的当前值赋给left，接着移动right直到整个数组被遍历完。
以下是Java的题解代码实现。
class Solution {
public List<String> summaryRanges(int[] nums) {
List<String> ranges = new ArrayList<>();
int left = 0, right = 0, N = nums.length;
if (N == 0)
return ranges;
while (right < N) {
if (right > 0 && nums[right] != nums[right-1]+1) {
ranges.add(range(nums[left], nums[right-1]));
left = right;
}
++right;
}
ranges.add(range(nums[left], nums[right-1]));
return ranges;
}
private String range(int begin, int end) {
if (begin == end) {
return String.format("%d", begin);
}
else {
return String.format("%d->%d", begin, end);
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
vector<string> ranges;
int left = 0, right = 0, N = nums.size();
if (N == 0)
return ranges;
while (right < N) {
if (right > 0 && nums[right] != nums[right-1]+1) {
ranges.push_back(range(nums[left], nums[right-1]));
left = right;
}
++right;
}
ranges.push_back(range(nums[left], nums[right-1]));
return ranges;
}
private:
string range(int begin, int end) {
if (begin == end) {
return to_string(begin);
}
else {
return to_string(begin)+"->"+to_string(end);
}
}
};