0228. Summary Ranges¶
题目信息¶
- 题号:
0228
- 难度:
Easy
- 主题:
数组、区间、顺序扫描、字符串格式
- 原题:
- 重点:
严格递增且无重复、最小连续区间、单点与区间的不同格式、整数边界
题目重述¶
给定一个已经严格递增且没有重复值的整数数组 nums,用若干互不重叠的连续整数区间恰好覆盖数组中的全部数字,并返回这些区间的字符串表示。每个数字只能属于一个返回区间,返回顺序与数组中的先后顺序一致。
若一个区间只包含单个整数 a,表示为 "a";若包含从 a 到 b 的至少两个连续整数,表示为 "a->b"。数组长度位于 [0, 20],元素可以达到 32 位有符号整数的最小值或最大值,因此判断相邻连续性时不能让 nums[i] + 1 发生溢出。
自建示例¶
混合单点与连续段:
输入:nums = [-3, -2, 0, 2, 3, 4, 7]
输出:["-3->-2", "0", "2->4", "7"]
解释:-3 与 -2 连续;0 和 7 各自孤立;2、3、4 构成一个完整连续段。
空数组:
输入:nums = []
输出:[]
解释:没有数字需要覆盖,因此返回空字符串数组。
一次扫描合并连续段¶
数组已经严格递增,所以一个区间从 nums[start] 开始向右延伸时,只需检查相邻元素是否连续。
当 nums[j+1] 不等于 nums[j]+1,当前段在 j 结束;下一段从 j+1 重新开始。
判断时把 nums[j] 转成 long long,避免当前值为 INT_MAX 时计算 nums[j]+1 溢出。
长度为 1 的段输出一个数字,长度大于 1 的段输出 start->end。由于每个元素只被一个正在构造的段覆盖,
扫描顺序天然保证区间不重叠且结果有序。
正确性说明¶
循环开始时 start 指向当前尚未输出段的第一个元素,i 扫描该段的末端。只要相邻差为 1,
严格递增数组中的中间整数没有缺失,可以继续合并;一旦不连续,任何跨过这个断点的区间都会包含缺失整数,
所以必须结束当前段。对每个段按其长度选择两种格式,循环结束后再输出最后一段,恰好覆盖全部输入值。
C++ 实现¶
class Solution {
public:
std::vector<std::string> summaryRanges(std::vector<int>& nums) {
std::vector<std::string> answer;
const int n = static_cast<int>(nums.size());
int start = 0;
while (start < n) {
int end = start;
while (end + 1 < n &&
static_cast<long long>(nums[end]) + 1 == nums[end + 1]) {
++end;
}
if (start == end) {
answer.push_back(std::to_string(nums[start]));
} else {
answer.push_back(std::to_string(nums[start]) + "->" +
std::to_string(nums[end]));
}
start = end + 1;
}
return answer;
}
};
代码分析¶
end 只向右移动,所有元素最多参与一次连续性判断,时间复杂度为 O(n);不计返回字符串本身,
额外工作空间为 O(1)。格式化输出的空间属于题目要求的结果,不用于保存额外的查找结构。