228. 汇总区间#

题目描述#

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

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

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

"a->b"，如果 a != b；
"a"，如果 a == b。

示例 1：

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

示例 2：

1
输入：nums = [0,2,3,4,6,8,9]
2
输出：["0","2->4","6","8->9"]

提示：

0 <= nums.length <= 20
-2^31 <= nums[i] <= 2^31 - 1

解题思路#

核心思想#

用分组循环把数组切成若干段「连续整数」区间：段内相邻元素差恒为 1。对每个段 [i, j]，若 nums[i] == nums[j] 则输出单个 "x"，否则输出 "x"->"y"。

分组示意（nums = [0,1,2,4,5,7]）：

1
[0,1,2] / [4,5] / [7]  →  "0->2" / "4->5" / "7"

算法步骤#

令 i = 0，初始化结果列表 res。
当 i < n 时：
- 记段起点 start = nums[i]；
- j = i，内层 while j+1 < n and nums[j+1] == nums[j] + 1 时 j++；
- 若 start == nums[j]，追加 str(start)；否则追加 f"{start}->{nums[j]}"；
- i = j + 1。
返回 res。

逐步举例#

以 nums = [0,2,3,4,6,8,9] 为例：

段起点 i	段终点 j	nums	输出
0	0	[0]	“0”
1	3	[2,3,4]	“2->4”
4	4	[6]	“6”
5	6	[8,9]	“8->9”

结果为 ["0","2->4","6","8->9"]。

复杂度分析#

时间复杂度：O(N)，单次线性扫描。
空间复杂度：O(1)（不计输出结果空间）。

代码实现#

1
from typing import List
2

3

4
class Solution:
5
    def summaryRanges(self, nums: List[int]) -> List[str]:
6
        res = []
7
        n = len(nums)
8
        i = 0
9
        while i < n:
10
            start = nums[i]
11
            j = i
12
            while j + 1 < n and nums[j + 1] == nums[j] + 1:
13
                j += 1
14
            if start == nums[j]:
15
                res.append(str(start))
16
            else:
17
                res.append(f"{start}->{nums[j]}")
18
            i = j + 1
19
        return res

1
import sys
2
from pathlib import Path
3

4
sys.path.insert(0, str(Path(__file__).parent))
5
import unittest
6

7
from solution import Solution
8

9

10
class TestSolution(unittest.TestCase):
11
    def test_example1(self):
12
        self.assertEqual(Solution().summaryRanges([0, 1, 2, 4, 5, 7]),
13
                         ["0->2", "4->5", "7"])
14

15
    def test_example2(self):
16
        self.assertEqual(Solution().summaryRanges([0, 2, 3, 4, 6, 8, 9]),
17
                         ["0", "2->4", "6", "8->9"])
18

19

20
if __name__ == '__main__':
21
    unittest.main()