汇总区间

标签: 数组

难度: Easy

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

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

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

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

示例 1：

输入：nums = [0,1,2,4,5,7]
输出：["0->2","4->5","7"]
解释：区间范围是：
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

示例 2：

输入：nums = [0,2,3,4,6,8,9]
输出：["0","2->4","6","8->9"]
解释：区间范围是：
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

提示：

  • 0 <= nums.length <= 20
  • -231 <= nums[i] <= 231 - 1
  • nums 中的所有值都 互不相同
  • nums 按升序排列

Submission

运行时间: 14 ms

内存: 15.9 MB

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        res = []
        if not nums:
            return res
        if len(nums) == 1:
            res.append(str(nums[0]))
            return res
        start = 0
        for i in range(len(nums)-1):
            if (nums[i] + 1) != nums[i + 1] :
                res.append(str(nums[start]) + '->' + str(nums[i]) if start != i else str(nums[i]))
                start = i + 1
        res.append(str(nums[start]) + '->' + str(nums[len(nums) - 1])if start != len(nums) - 1 else str(nums[len(nums) - 1]))
        return res

Explain

这个题解的思路是使用一次遍历来找出连续数字的区间范围。具体做法是维护一个 start 变量记录当前区间的起始位置，然后遍历数组，如果当前数字和下一个数字不连续，就将当前区间 [start, i] 加入结果，并将 start 更新为下一个数字的位置 i+1。遍历结束后，还需要将最后一个区间加入结果。在加入结果时，要根据区间的起始和结束位置是否相同，来决定输出的格式是 'a->b' 还是 'a'。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        res = []
        if not nums:
            return res
        if len(nums) == 1:
            res.append(str(nums[0]))
            return res
        
        start = 0  # 记录当前区间的起始位置
        for i in range(len(nums)-1):
            if (nums[i] + 1) != nums[i + 1] :  # 如果当前数字和下一个数字不连续
                # 将当前区间加入结果
                res.append(str(nums[start]) + '->' + str(nums[i]) if start != i else str(nums[i]))
                start = i + 1  # 更新 start 为下一个数字的位置
        
        # 将最后一个区间加入结果
        res.append(str(nums[start]) + '->' + str(nums[len(nums) - 1]) if start != len(nums) - 1 else str(nums[len(nums) - 1]))
        
        return res

Explore

当数组仅含有一个元素时，该元素自身既是区间的起始也是结束。因此，直接将该单个元素转换为字符串后加入到结果列表中。在代码中，首先检查数组长度是否为1，如果是，则创建一个只包含此单个元素字符串的结果列表并返回它。

如果输入数组为空，那么没有任何区间需要被添加到结果列表中。在代码中，首先检查数组是否为空，如果是，则直接返回一个空的列表。这样处理是基于对函数返回值类型一致性的考虑，确保所有情况下都返回一个列表，符合函数的预期输出类型。

区间的结束通过检测当前元素与下一个元素是否连续来确定。如果当前元素与下一个元素不连续（即当前元素加一不等于下一个元素），则当前元素是区间的结束。此时，将从 'start' 到当前索引 'i' 的区间加入到结果列表中，并更新 'start' 为下一个元素的索引，即 'i+1'。这样可以确保每个连续的数字范围都被正确地识别和记录。

在数组中，当数字2和数字4不连续时，数字2是一个区间的结束。根据我们的检测逻辑，由于2加1不等于4，我们认定这里区间结束。因此，会将从上一个记录的起始位置到当前位置（此例中为从0到2）的区间加入结果列表，并更新起始位置为下一个元素的位置，即4的索引。这种处理确保了每个连续区间被正确分割并加入到结果列表中。