228. 汇总区间
题目描述
输入一个严格递增的整数数组 nums，其中没有重复的值。
把数组中的数分成若干段，每段都是一串连续的整数 [a,b]（包含两端）。要求每个数恰好属于一段，任何一段里都不能出现 nums 之外的数。在此前提下，段数要尽量少。
按从小到大的顺序返回这些段组成的字符串列表。某段的 a != b 时写成 "a->b"；a == b 时只写 "a"。数组为空时返回空列表。
示例 1
输入：nums = [0,1,2,4,5,7] 输出：["0->2","4->5","7"]
解释：三段分别是 [0,2]、[4,5]、[7,7]，对应 "0->2"、"4->5"、"7"。
示例 2
输入：nums = [0,2,3,4,6,8,9] 输出：["0","2->4","6","8->9"]
解释：四段分别是 [0,0]、[2,4]、[6,6]、[8,9]。
数据范围
0 <= nums.length <= 20-2^31 <= nums[i] <= 2^31 - 1nums中的数两两不同。nums已按升序排好。
解题思路
数组有序且无重复，所以一段连续整数在数组里一定是相邻的一串。用 i 标记一段的起点，j 从 i 出发不断向右延伸，只要下一个数恰好比当前大 1 就继续。延伸停止时 nums[i..j] 就是一个最长连续段：i == j 输出单个数，否则输出 "nums[i]->nums[j]"。然后从 j+1 开始找下一段。
为什么正确
每次外层循环开始时，nums[0..i-1] 已被 res 中的区间恰好覆盖，且每个区间都无法再向右延长。
复杂度分析
时间 O(n)（每个元素只被 j 经过一次），除结果外空间 O(1)。
易错点
单个数字不要写成 "7->7"；判断连续时用 nums[j+1] == nums[j] + 1，在 C++/Java 中要防止 nums[j] + 1 溢出（INT_MAX 时）；数组为空时直接返回空列表。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def summaryRanges(self, nums: List[int]) -> List[str]:
res = []
i, n = 0, len(nums)
while i < n:
j = i
while j + 1 < n and nums[j + 1] == nums[j] + 1:
j += 1
if i == j:
res.append(str(nums[i]))
else:
res.append(str(nums[i]) + "->" + str(nums[j]))
i = j + 1
return resclass Solution {
public List<String> summaryRanges(int[] nums) {
List<String> res = new ArrayList<>();
int i = 0, n = nums.length;
while (i < n) {
int j = i;
while (j + 1 < n && (long) nums[j + 1] == (long) nums[j] + 1) {
j++;
}
if (i == j) {
res.add(String.valueOf(nums[i]));
} else {
res.add(nums[i] + "->" + nums[j]);
}
i = j + 1;
}
return res;
}
}class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
vector<string> res;
int i = 0, n = nums.size();
while (i < n) {
int j = i;
while (j + 1 < n && (long long)nums[j + 1] == (long long)nums[j] + 1) {
j++;
}
if (i == j) {
res.push_back(to_string(nums[i]));
} else {
res.push_back(to_string(nums[i]) + "->" + to_string(nums[j]));
}
i = j + 1;
}
return res;
}
};func summaryRanges(nums []int) []string {
res := []string{}
i, n := 0, len(nums)
for i < n {
j := i
for j+1 < n && nums[j+1] == nums[j]+1 {
j++
}
if i == j {
res = append(res, strconv.Itoa(nums[i]))
} else {
res = append(res, strconv.Itoa(nums[i])+"->"+strconv.Itoa(nums[j]))
}
i = j + 1
}
return res
}var summaryRanges = function(nums) {
const res = [];
let i = 0, n = nums.length;
while (i < n) {
let j = i;
while (j + 1 < n && nums[j + 1] === nums[j] + 1) {
j++;
}
if (i === j) {
res.push(String(nums[i]));
} else {
res.push(nums[i] + "->" + nums[j]);
}
i = j + 1;
}
return res;
};function summaryRanges(nums: number[]): string[] {
const res: string[] = [];
let i = 0, n = nums.length;
while (i < n) {
let j = i;
while (j + 1 < n && nums[j + 1] === nums[j] + 1) {
j++;
}
if (i === j) {
res.push(String(nums[i]));
} else {
res.push(nums[i] + "->" + nums[j]);
}
i = j + 1;
}
return res;
}