0228. Summary Ranges
====================
题目信息
--------
:题号: 0228
:难度: Easy
:主题: 数组、区间、顺序扫描、字符串格式
:原题: `LeetCode 0228 `_
:重点: 严格递增且无重复、最小连续区间、单点与区间的不同格式、整数边界
题目重述
--------
给定一个已经严格递增且没有重复值的整数数组 ``nums``,用若干互不重叠的连续整数区间恰好覆盖数组中的全部数字,并返回这些区间的字符串表示。每个数字只能属于一个返回区间,返回顺序与数组中的先后顺序一致。
若一个区间只包含单个整数 ``a``,表示为 ``"a"``;若包含从 ``a`` 到 ``b`` 的至少两个连续整数,表示为 ``"a->b"``。数组长度位于 ``[0, 20]``,元素可以达到 32 位有符号整数的最小值或最大值,因此判断相邻连续性时不能让 ``nums[i] + 1`` 发生溢出。
自建示例
--------
混合单点与连续段:
.. code-block:: text
输入:nums = [-3, -2, 0, 2, 3, 4, 7]
输出:["-3->-2", "0", "2->4", "7"]
解释:-3 与 -2 连续;0 和 7 各自孤立;2、3、4 构成一个完整连续段。
空数组:
.. code-block:: text
输入: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++ 实现
--------
.. code-block:: cpp
class Solution {
public:
std::vector summaryRanges(std::vector& nums) {
std::vector answer;
const int n = static_cast(nums.size());
int start = 0;
while (start < n) {
int end = start;
while (end + 1 < n &&
static_cast(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)``。格式化输出的空间属于题目要求的结果,不用于保存额外的查找结构。