Summary Ranges
你会得到一个由互不相同的整数构成的有序数组 nums。将它拆分成尽可能少的连续整数范围，使每个值恰好属于一个范围。将范围 a..b 写成文本 "a->b"；如果范围只包含一个值，则写成 "a"。按递增顺序返回这些范围。
函数
- numsinteger-array
- 排序后的互不相同的整数数组
- 返回值string-array
- 以文本形式表示范围，从最小值到最大值
约束条件
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109nums按升序排列，且没有重复项。
示例
- 输入
- nums = [0, 1, 2, 5, 6, 9]
- 输出
- ["0->2", "5->6", "9"]
- 解释
0, 1, 2是连续的，因此它们组成"0->2"。从 2 跳到 5 时，会开始一个新的范围"5->6"，而 9 则单独表示为"9"。
- 输入
- nums = [-3, -1, 0, 1, 4, 7, 8]
- 输出
- ["-3", "-1->1", "4", "7->8"]
- 解释
- -3 没有相邻的值（缺少 -2），
-1, 0, 1构成一个连续段，4 单独存在，7, 8结束了这个列表。负值的处理方式相同：-1 后面是 -1 + 1 = 0。
进阶
假设 nums 中可能有重复值，例如 [1, 2, 2, 3]。你需要做什么修改，才能让它仍然输出 "1->3"？
提示
逐个打开提示，每个都会多透露一点。
数组已排序。相邻的两个值在什么情况下属于同一个范围？
当且仅当
nums[i+1] == nums[i] + 1时，它们属于同一组。其他相邻元素对都标志着一个范围的结束和下一个范围的开始。记住当前范围的起点。向前遍历，只要下一个值比当前值大 1，就继续；当连续序列中断或到达数组末尾时，写出从起点到当前值的范围，并将下一个值作为下一个范围的起点。
题解
由于这些值已排序且互不相同，一段连续整数在数组中就是一段相邻数，它恰好在两个相邻数之差大于 1 的地方结束。没有任何一段范围能跨过这样的间隔，因此在每个间隔处切分，就能得到最少的范围。
检查每个值的两个相邻值
思路
区间从第一个值开始，或者从左侧相邻值不是它减 1 的值开始。区间在最后一个值处结束，或者在右侧相邻值不是它加 1 的值处结束。在 [0, 1, 2, 5, 6, 9] 中，区间从 0、5 和 9 开始，在 2、6 和 9 结束。
记住当前区间开始处的值。当区间在 nums[i] 处结束时，写入 "start->nums[i]"；如果区间在同一个值处开始和结束，就只写入 "start"，例如 9。
每个值只检查一次它的两个相邻值：时间复杂度为 O(n)，只需记住一个开始值，额外空间复杂度为 O(1)。
算法
- 将
start = nums[0]设为起始值。 - 对于每个索引
i：如果i > 0且nums[i] != nums[i-1] + 1，则将start = nums[i]设为起始值。 - 如果
i是最后一个索引，或者nums[i+1] != nums[i] + 1，则范围在此处结束。 - 当
start == nums[i]时，追加"start"，否则追加"start->nums[i]"。 - 返回最后一个索引之后的列表。
def summaryRanges(nums):
n = len(nums)
ranges = []
start = nums[0]
for i in range(n):
# A range opens where the value before is not one less.
if i > 0 and nums[i] != nums[i - 1] + 1:
start = nums[i]
# A range closes where the value after is not one more.
if i == n - 1 or nums[i + 1] != nums[i] + 1:
ranges.append(str(start) if start == nums[i] else f"{start}->{nums[i]}")
return ranges用两个指针遍历每个连续段
思路
找出每个区间的两个端点。指针 i 指向第一个值。指针 j 从 i 开始向右移动，只要下一个值恰好大 1，就继续移动，因此它会停在最后一个值上。然后 i 跳到 j+1。
对于 [-3, -1, 0, 1, 4, 7, 8]：在 -3 处，下一个值 -1 不是 -2，所以 "-3" 单独成段。从 -1 开始，j 越过 0 和 1，在 4 之前停下："-1->1"。接下来是 "4" 和 "7->8"。
两个指针都只向前移动，因此内层循环总共运行 n 次：时间复杂度为 O(n)，额外空间复杂度为 O(1)。
算法
- 将
i = 0。 - 设置
j = i，并在j+1 < n且nums[j+1] == nums[j] + 1时，将j向右移动。 - 当
i == j时，追加"nums[i]"；否则追加"nums[i]->nums[j]"。 - 设置
i = j + 1，并重复操作，直到i超过末尾。 - 返回列表。
def summaryRanges(nums):
ranges = []
n = len(nums)
i = 0
while i < n:
# i is the first value of a run; push j to its last value.
j = i
while j + 1 < n and nums[j + 1] == nums[j] + 1:
j += 1
ranges.append(str(nums[i]) if i == j else f"{nums[i]}->{nums[j]}")
# The next run starts right after this one.
i = j + 1
return ranges
易错点和边界情况
- 忘记处理最后一个范围。如果循环只在遇到间隔时写入范围，就永远不会写入最后一个范围，因此
[0, 1, 2, 5, 6, 9]中的"9"会丢失。也要在最后一个索引处结束一个范围。 - 将单个值写成
"a->a"。只有一个值的范围应写成"a"。 - 以科学计数法打印较大的值。R 会将类似
1000000000的双精度数转换为1e+09；粘贴这些值之前，先将它们转换为整数。
常见问题3
Summary Ranges 的时间复杂度是多少？
O(n)。每个值都会访问一次，每个范围都会写入一次。除输出列表外，额外空间为 O(1)：当前范围的起点和一两个索引。
如何处理只有一个数字的范围？
检查范围的起始值和结束值是否相同。如果相同，就只写这个值，例如 "9"。如果不同，就写起始值、箭头和结束值，例如 "5->6"。使用两个指针时，判断条件是 i == j。
Summary Ranges 需要输入按顺序排列吗？
是的。这个方法只比较相邻的值，因此它依赖连续整数彼此相邻。对于未排序的输入，先对它排序，这会使任务的时间复杂度达到 O(n log n)；或者像最长连续序列问题那样，把这些值放进哈希集合，并从每个范围的最小值开始扩展。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def summaryRanges(nums):
# 在这里编写代码测试 #1
测试 #2
参数
nums = [0, 1, 2, 5, 6, 9]
预期输出
["0->2", "5->6", "9"]