题目描述
给定一个整数数组 nums,返回所有唯一的区间,这些区间包含数组中的每个数字,形式为 [a, b],其中 a 和 b 是数字的最小和最大值。
示例
示例 1:
输入: nums = [0,1,2,4,5,7]
输出: [["0,2"],["4,5"],["7"]]
解释:
区间 [0,2] 包含数字 0, 1, 2。
区间 [4,5] 包含数字 4, 5。
数字 7 作为单独的区间。
示例 2:
输入: nums = [0,2,3,4,6,8,9]
输出: [["0,2"],["3,4"],["6","8"],["9"]]
解释:
区间 [0,2] 包含数字 0, 2。
区间 [3,4] 包含数字 3, 4。
数字 6 是单个区间。
数字 8 是单个区间。
数字 9 是单个区间。
题解
这个问题可以通过遍历数组并跟踪当前区间的开始和结束来解决。
- 初始化:创建一个空列表 result 来存储区间。
- 遍历数组:从数组的第一个元素开始遍历。
○ 使用两个指针 start 和 end 来跟踪当前区间的开始和结束。
○ 如果当前元素与前一个元素连续,则更新 end。
○ 如果当前元素不连续,则将当前区间 [start, end] 添加到 result 中,并重置 start 和 end。 - 处理最后一个区间:遍历结束后,将最后一个区间添加到 result 中。
- 返回结果:返回 result。
代码实现
vector<string> summaryRanges(vector<int>& nums) {
vector<string> result;
if (nums.empty())
return result;
int start = nums[0], end = nums[0];
for (int i = 1; i < nums.size(); i++) {
if (nums[i] == end + 1) {
end = nums[i];
} else {
if (start == end) {
result.push_back(to_string(start));
} else {
result.push_back(to_string(start) + "->" + to_string(end));
}
start = end = nums[i];
}
}
if (start == end) {
result.push_back(to_string(start));
} else {
result.push_back(to_string(start) + "->" + to_string(end));
}
return result;
}
复杂度分析
● 时间复杂度:O(n),其中 n 是数组 nums 的长度。我们需要遍历一次数组。
● 空间复杂度:O(m),其中 m 是输出区间的数量。我们需要存储每个区间。
这个算法的优势在于它只需要一次遍历即可找到所有区间,且不需要额外的存储空间。