---

0228. 汇总区间

• 标签：数组
• 难度：简单

题目链接

• 0228. 汇总区间 - 力扣

题目大意

描述：

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

区间 $[a, b]$ 是从 $a$ 到 $b$（包含）的所有整数的集合。

要求：

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

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

• "a->b" ，如果 $a \ne b$。
• "a"，如果 $a == b$。

说明：

• $0 \le nums.length \le 20$。
• $-2^{31} \le nums[i] \le 2^{31} - 1$。
• $nums$ 中的所有值都 互不相同。
• $nums$ 按升序排列。

示例：

• 示例 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"

解题思路

思路 1：双指针

使用双指针遍历数组，找到连续区间的起始和结束位置。

具体步骤：

1. 初始化结果列表 $res$ 和双指针 $i = 0$。
2. 遍历数组，对于每个位置 $i$：
   • 记录当前区间的起始位置 $start = nums[i]$。
   • 移动指针 $j$ 直到 $nums[j + 1] \neq nums[j] + 1$ 或到达数组末尾。
   • 记录当前区间的结束位置 $end = nums[j]$。
   • 根据 $start$ 和 $end$ 的关系生成区间字符串：
     • 如果 $start = end$，添加 $"start"$。
     • 否则，添加 $"start->end"$。
   • 更新 $i = j + 1$ 继续处理下一个区间。

思路 1：代码

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        if not nums:
            return []
        
        res = []
        i = 0
        n = len(nums)
        
        while i < n:
            # 记录当前区间的起始位置
            start = nums[i]
            
            # 找到连续区间的结束位置
            j = i
            while j + 1 < n and nums[j + 1] == nums[j] + 1:
                j += 1
            
            # 记录当前区间的结束位置
            end = nums[j]
            
            # 根据起始和结束位置生成区间字符串
            if start == end:
                res.append(str(start))
            else:
                res.append(f"{start}->{end}")
            
            # 移动到下一个区间的起始位置
            i = j + 1
        
        return res

思路 1：复杂度分析

• 时间复杂度：$O(n)$。每个元素最多被访问两次（作为区间起点和终点），总体时间复杂度为 $O(n)$。
• 空间复杂度：$O(1)$。除了结果数组外，只使用了常数级别的额外空间。