泰安市住房和城乡建设局网站汕头百度网络推广
题目描述
给定一个整数数组 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 是输出区间的数量。我们需要存储每个区间。
这个算法的优势在于它只需要一次遍历即可找到所有区间，且不需要额外的存储空间。