228. 汇总区间

🟢   🔖  数组  🔗 力扣 LeetCode

题目

You are given a sorted unique integer array nums.

A range [a,b] is the set of all integers from a to b (inclusive).

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

Example 1:

Input: nums = [0,1,2,4,5,7]

Output: ["0->2","4->5","7"]

Explanation: The ranges are:

[0,2] --> "0->2"

[4,5] --> "4->5"

[7,7] --> "7"

Example 2:

Input: nums = [0,2,3,4,6,8,9]

Output: ["0","2->4","6","8->9"]

Explanation: The ranges are:

[0,0] --> "0"

[2,4] --> "2->4"

[6,6] --> "6"

[8,9] --> "8->9"

Constraints:

• 0 <= nums.length <= 20
• -2^31 <= nums[i] <= 2^31 - 1
• All the values of nums are unique.
• nums is sorted in ascending order.

题目大意

给定一个 无重复元素 的 有序 整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

• "a->b" ，如果 a != b
• "a" ，如果 a == b

解题思路

• 因为数组是有序的，可以遍历数组里的每个数 i ，以其为起点，寻找 i+1, i+2, i+3...是否存在，并不断记录：
  • 若 i+1 不存在，直接将 i 加入返回数组中；
  • 若 i+1 存在，则以 i 为起点开始枚举，直到 i + n 不存在时，再将 i + '->' + (i + n - 1) 加入返回数组中；
• 为了降低遍历数组的时间复杂度，可以将数组中的数存在哈希表中，这样查看一个数是否存在的时间复杂度可以优化到 O(1)；

复杂度分析

• 时间复杂度：O(n)，其中 n 是输入数组的长度，需要遍历数组一次。
• 空间复杂度：O(n)，使用了一个哈希表来存储数组中的数。

代码

/**
 * @param {number[]} nums
 * @return {string[]}
 */
var summaryRanges = function (nums) {
	let set = new Set(nums),
		res = [];
	for (let i = 0; i < nums.length; i++) {
		let num = nums[i],
			str = '' + num;
		if (!set.has(num + 1)) {
			res.push(str);
		} else {
			let len = 1;
			while (set.has(num + len)) {
				len++;
				i++;
			}
			res.push(str + '->' + (num + len - 1));
		}
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度
163	缺失的区间 🔒		数组
352	将数据流变为多个不相交区间		设计 二分查找 有序集合
2655	寻找最大长度的未覆盖区间 🔒		数组 排序