LeetCode 228. 汇总区间

2021-12-23 HGNULB 约 10 分钟

文章信息 7 个分类 1 个标签

分类

题目描述

✅ 228. 汇总区间

题意分析

给定一个无重复元素且已升序排列的整数数组 nums，要求把它切成若干段「恰好覆盖数组中全部数字、且每段内部数字连续」的最小区间集合，按顺序输出。长度为 1 的区间写成 "a"，长度大于 1 的写成 "a->b"。

「最小区间集合」加上「恰好覆盖」这两个约束合起来，其实唯一确定了答案：只要两个相邻数字差 1 就必须放进同一段，差大于 1 就必须断开。所以这题没有选择空间，也不需要任何搜索或贪心决策，本质是一次分段扫描。

约束里「已升序、无重复」是最重要的信号。有序意味着连续性只需检查相邻两项，不必回头看；无重复意味着相邻两项之差至少是 1，于是「差等于 1」和「差大于 1」构成完备的二分情况，不存在差为 0 的第三种。如果去掉这两个前提，就得先排序去重，题目性质会完全改变。

输出是字符串而不是数字，所以还有一层格式责任：单点区间不能写成 "1->1"，必须写成 "1"。这是本题除了分段之外的第二个考点。

数值范围给到 32 位整数全域，这意味着 nums 里可能同时出现 -2147483648 和 2147483647。任何写成 nums[i] - nums[i-1] == 1 的判断都要留意减法溢出，而写成 nums[i] == nums[i-1] + 1 时加法同样可能溢出——需要明确哪种写法在什么情况下安全。

边界有三处：空数组返回空列表；单元素数组返回一个单点区间；整个数组完全连续时返回唯一一段。另外，无论数组怎么切，最后一段永远不会被「遇到断层」触发结算，必须在循环外补一次收尾。

解法：双指针线性扫描

核心思路

朴素想法是「先找出所有断点位置，再根据断点切数组，最后逐段格式化」。这需要两趟遍历和一个额外的断点数组，虽然复杂度一样，但把一件事拆成了三件，代码更长也更容易在切分下标上出错。瓶颈不在时间而在状态被外置了：断点数组其实只是把「当前段从哪开始」这一个变量存成了一整个列表。

由此得到简化的观察：任何时刻真正需要知道的只有两件事——当前这一段的起点是谁，以及当前这一段目前扩到了哪个数。前者决定区间左端，后者用来和下一个数比较判断是否断开。于是用两个变量 start 和 prev 就足够，一趟扫描即可。

循环不变量是：处理下标 i 前，所有更早的完整区间都已写入答案；[start, prev] 是唯一尚未结算的连续区间，覆盖从当前段首到 nums[i-1] 的所有值。 start、prev 保存的是数值，不是数组下标。

每轮只有两种情况：若当前值与 prev 的 64 位差等于 1，就把当前段延伸到 nums[i]；否则先结算 [start, prev]，再以 nums[i] 开启新段。使用 64 位中间值能让连续性判断在 32 位整数边界上也保持直观可靠。

循环退出时 i 越过末尾，不变量告诉我们仍有一段 [start, prev] 尚未结算——因为结算只发生在「遇到断层」时，而数组末尾没有下一个元素来制造断层。所以循环外必须补一次 formatRange(start, prev)，这不是可选的优化而是不变量的必然推论。

格式化单独抽成一个函数，判据是 start == end：相等说明这一段只有一个数字，输出单个数；否则输出 "start->end"。抽出来的好处是循环里和循环外两处结算共用同一份格式逻辑，不会出现两处写法不一致。

解题步骤

先处理空数组：nums.length == 0 时直接返回空列表。为什么必须提前返回——下一步要读 nums[0] 来初始化，空数组会越界。这是本题唯一真正需要的特判。

初始化 start = nums[0]、prev = nums[0]：为什么两者都取 nums[0] 而不是让 prev 取某个哨兵值——第一个元素必然属于第一段，把它同时当作段起点和段末尾，不变量在循环开始前就成立了；若给 prev 一个如 Integer.MIN_VALUE 的哨兵，反而会在第一轮制造出一次假断层。

从下标 1 开始遍历：为什么从 1 而不是 0——下标 0 已经在初始化里被吸收进当前段，从 0 开始会让第一个元素和自己比较。

延伸分支：先提升为 64 位，再判断 nums[i] - prev == 1。成立时只更新 prev；start 保持不变。

断层分支：先把 [start, prev] 结算进答案，再把 start、prev 一起重置为 nums[i]。为什么必须先结算再重置——顺序反了会把旧段的起点丢掉，输出的区间左端变成新段的起点。

循环结束后再结算一次：为什么不能省——最后一段没有后继元素来触发断层分支，只能在循环外收尾。这是本题最高频的遗漏点。

格式化按 start == end 分支：相等输出单个数字，否则拼 "->"。为什么不能统一写成 "start->end"——题目对单点区间的格式有明确要求，写成 "1->1" 直接判错。

以 nums = [0,1,2,4,5,7] 走一遍。

初始化：start = 0，prev = 0，答案为空。
i=1，nums[1]=1，prev+1=1，相等，延伸，prev=1。当前段 [0,1]。
i=2，nums[2]=2，prev+1=2，相等，延伸，prev=2。当前段 [0,2]。
i=3，nums[3]=4，prev+1=3，不等，断层：结算 [0,2]，因 0 != 2 格式化为 "0->2" 写入答案；重置 start=4、prev=4。
i=4，nums[4]=5，prev+1=5，相等，延伸，prev=5。当前段 [4,5]。
i=5，nums[5]=7，prev+1=6，不等，断层：结算 [4,5] 得 "4->5" 写入答案；重置 start=7、prev=7。
循环结束，答案里是 ["0->2","4->5"]，而最后一段 [7,7] 还没结算。循环外补一次：start == prev == 7，格式化为单点 "7"。

最终返回 ["0->2","4->5","7"]，与期望一致。若漏掉循环外的收尾，返回值会是 ["0->2","4->5"]，末尾区间凭空消失——这正是必须补结算的直接证据。

再用 nums = [0,2,3,4,6,8,9] 快速验证单点与多点混排：i=1 断层结算 [0,0] 得 "0"；i=2、i=3 延伸到 prev=4；i=4 断层结算 [2,4] 得 "2->4"；i=5 断层结算 [6,6] 得 "6"；i=6 延伸到 prev=9；循环外结算 [8,9] 得 "8->9"。答案 ["0","2->4","6","8->9"]。

代码实现

import java.util.ArrayList;
import java.util.List;

// 当前值与 prev 的 64 位差不为 1 时，结算 [start, prev]。
class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<>();
        if (nums.length == 0) {
            return res;
        }

        int start = nums[0];
        int prev = nums[0];

        for (int i = 1; i < nums.length; i++) {
            if ((long) nums[i] - prev == 1) {
                prev = nums[i];
                continue;
            }

            res.add(formatRange(start, prev));
            start = nums[i];
            prev = nums[i];
        }

        res.add(formatRange(start, prev));
        return res;
    }

    private String formatRange(int start, int end) {
        if (start == end) {
            return String.valueOf(start);
        }
        return start + "->" + end;
    }
}

import "strconv"

// 当前值与 prev 的 64 位差不为 1 时，结算 [start, prev]。
func summaryRanges(nums []int) []string {
	res := []string{}
	if len(nums) == 0 {
		return res
	}

	start := nums[0]
	prev := nums[0]

	for i := 1; i < len(nums); i++ {
		if int64(nums[i])-int64(prev) == 1 {
			prev = nums[i]
			continue
		}
		res = append(res, formatRange(start, prev))
		start = nums[i]
		prev = nums[i]
	}

	res = append(res, formatRange(start, prev))
	return res
}

func formatRange(start int, end int) string {
	if start == end {
		return strconv.Itoa(start)
	}
	return strconv.Itoa(start) + "->" + strconv.Itoa(end)
}

复杂度分析

时间复杂度：$O(n)$，$n$ 为数组长度。凭什么：每个元素只在循环里被访问一次，两个分支内部都是常数次赋值；结算次数等于区间个数，不超过 $n$，每次格式化的字符串长度受整数位数限制为常数。

空间复杂度：$O(1)$ 额外空间，不计返回值。凭什么：全程只维护 start、prev 两个整型变量，没有辅助数组或递归栈；返回列表本身最多存 $n$ 个字符串，这是输出规模而非算法开销。

关键点总结

「分段扫描」类问题的通用骨架是：用少量变量描述当前段，遇到分段条件就结算并重置，循环外补一次收尾。收尾这一步是骨架的固定组成部分，不是特例。

连续性判断使用 64 位中间差值，避免让 32 位边界影响分段条件。

把格式化逻辑抽成独立函数，让循环内与循环外两处结算共用同一份实现，避免两处格式规则不一致——这是消除重复分支的常规手段。

初始化时让不变量在第一轮之前就成立（这里是把 nums[0] 同时赋给 start 和 prev），往往能消掉一个特判；用哨兵值反而容易制造出假的第一次触发。

有序 + 无重复的前提要在分析阶段明确说出来，因为它保证了「差等于 1」与「差大于 1」两分支完备。前提变了（比如允许重复），代码结构就要跟着变。

面试表达重点是：当前段状态、断层时先结算后重置、循环结束必须收尾，以及单点与多点的格式分支。

易错点总结

忘记循环结束后再结算一次：用例 [0,1,2,4,5,7]，只在断层处结算会得到 ["0->2","4->5"]，末尾的 "7" 完全丢失；用例 [1,2,3] 更极端，全程没有断层，返回的是空列表。

单点区间也写成 "a->b"：用例 [0,2,3]，正确答案是 ["0","2->3"]，统一格式化会输出 ["0->0","2->3"]，第一项格式不符判错。

没处理空数组就读 nums[0]：用例 []，初始化 start = nums[0] 直接抛数组越界（Go 版是 index out of range panic）。

断层分支里先重置 start 再结算：用例 [0,1,3]，i=2 时若先把 start 改成 3 再调用 formatRange(start, prev)，会输出 "3->1"，左右端点颠倒。

断层时只重置了 start 忘记重置 prev：用例 [0,1,3,4]，i=2 后 prev 仍停在 1，i=3 时判断 4 == 1 + 1 不成立，会把 [3,3] 和 [4,4] 拆成两段，输出 ["0->1","3","4"] 而非 ["0->1","3->4"]。

循环从下标 0 开始：用例 [0,1,2]，i=0 时判断 0 == prev + 1 即 0 == 1 不成立，立刻触发一次假断层，把首元素单独结算成 "0"，输出 ["0","0->2"]，首元素被算了两次。

用 32 位差值判断 nums[i] - prev > 1：[-2147483648,2147483647] 的差会溢出为负数，可能被误判为没有断层；先转 64 位再相减。

相似题目

题目	难度	考察点
163. 缺失的区间	简单	输出的是数组的补集区间，要额外处理 `lower`/`upper` 两端的哨兵边界
56. 合并区间	中等	输入是无序区间而非有序点，必须先按左端点排序，合并条件变成区间是否相交
57. 插入区间	中等	在已有序区间中插入一段，考察三段式扫描与只遍历一次的边界拼接
128. 最长连续序列	中等	输入无序且不许排序，要用哈希集合从段首起跳，把连续性判断从相邻改成查找
674. 最长连续递增序列	简单	分段条件从「差 1」放宽为「递增」，只要长度不要区间，可省掉 `start`
485. 最大连续 1 的个数	简单	分段条件是元素取值而非相邻关系，同样的骨架但结算的是段长最大值
1446. 连续字符	简单	分段条件是字符相等，结算改为取最大段长，可直接复用本题的双变量扫描模板