企业官网建设流程全解析

• 教程
• 文档
• 知识库

本篇技术指南基于 AlgoNote 算法通关手册中 0352. 将数据流变为多个不相交区间 的题解，深入讲解如何设计一个SummaryRanges类，把动态输入的非负整数数据流实时总结为不相交区间列表。读完本篇，你将掌握「哈希集合去重 + 排序后线性扫描合并区间」的经典设计思路、对应的完整可运行 Python 实现，并能理解其在大量合并、区间数量稀少场景下的优化方向。

一、题目回顾：数据流与不相交区间

描述：给定一个由非负整数 $a1, a2, ..., an$ 组成的数据流输入，需要将到目前为止看到的数字总结为不相交的区间列表。

要求：实现SummaryRanges类：

• SummaryRanges()使用一个空数据流初始化对象。
• void addNum(int val)向数据流中加入整数 $val$。
• int[][] getIntervals()以不相交区间 $[start_i, end_i]$ 的列表形式返回对数据流中整数的总结。

说明：

• $0 \le val \le 10^{4}$。
• 最多调用addNum和getIntervals方法 $3 \times 10^{4}$ 次。
• 进阶：如果存在大量合并，并且与数据流的大小相比，不相交区间的数量很小，该怎么办？

示例：

输入： ["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"] [[], [1], [], [3], [], [7], [], [2], [], [6], []] 输出： [null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]] 解释： SummaryRanges summaryRanges = new SummaryRanges(); summaryRanges.addNum(1); // arr = [1] summaryRanges.getIntervals(); // 返回 [[1, 1]] summaryRanges.addNum(3); // arr = [1, 3] summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3]] summaryRanges.addNum(7); // arr = [1, 3, 7] summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3], [7, 7]] summaryRanges.addNum(2); // arr = [1, 2, 3, 7] summaryRanges.getIntervals(); // 返回 [[1, 3], [7, 7]] summaryRanges.addNum(6); // arr = [1, 2, 3, 6, 7] summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]

从示例可以直观看出关键规律：数字1、2、3连续，合并为[1, 3]；数字6、7连续，合并为[6, 7]。所谓「不相交区间」，本质就是值域上连续的一段整数，这正是本仓库中「区间类问题」一贯的处理对象。

二、解题思路：集合 + 动态生成区间

这道题的核心是维护一个数字集合，然后在需要时动态生成不相交的区间列表。其标签为「设计、二分查找、有序集合」，在本题解中我们先从最简单、最易于验证正确性的「集合 + 动态生成」方案讲起。

2.1 算法思路

1. 数据结构选择：使用集合（set）存储所有出现过的数字，利用集合的去重特性自动处理重复数字——同一个数字多次addNum只保留一份，不会影响区间划分。
2. 添加数字：当添加数字 $val$ 时，直接将其加入集合中，时间复杂度为 $O(1)$。
3. 获取区间：当需要获取区间列表时：
   • 将集合中的所有数字排序。
   • 遍历排序后的数字，连续的数字合并为一个区间。
   • 遇到不连续的数字时，开始新的区间。

2.2 具体步骤

1. 使用集合存储所有添加的数字。
2. addNum(val)：将 $val$ 添加到集合中。
3. getIntervals()：
   • 对集合中的数字排序得到 $sorted_nums$。
   • 初始化 $start = end = sorted_nums[0]$。
   • 遍历剩余数字，如果 $sorted_nums[i] = end + 1$，则扩展当前区间 $end = sorted_nums[i]$。
   • 否则，保存当前区间 $[start, end]$，开始新区间 $start = end = sorted_nums[i]$。
   • 最后添加最后一个区间。

这一「排序 → 扫描 → 按连续性切分」的流程，与仓库中 0228. 汇总区间 的「双指针」思路同源：后者对静态有序数组用nums[j + 1] == nums[j] + 1判断连续性，前者对动态无序集合先排序再判断sorted_nums[i] == end + 1，两者共用同一个核心不变量——后一个数恰好比前一个数大 1 时合并。

2.3 代码

class SummaryRanges: def __init__(self): # 使用集合存储所有出现过的数字 self.nums = set() def addNum(self, value: int) -> None: # 将数字添加到集合中，集合自动去重 self.nums.add(value) def getIntervals(self) -> List[List[int]]: # 如果集合为空，返回空列表 if not self.nums: return [] # 将集合中的数字排序 sorted_nums = sorted(self.nums) intervals = [] # 初始化第一个区间 start = end = sorted_nums[0] # 遍历剩余数字，构建区间 for i in range(1, len(sorted_nums)): if sorted_nums[i] == end + 1: # 当前数字与前一个数字连续，扩展当前区间 end = sorted_nums[i] else: # 当前数字与前一个数字不连续，保存当前区间并开始新区间 intervals.append([start, end]) start = end = sorted_nums[i] # 添加最后一个区间 intervals.append([start, end]) return intervals # Your SummaryRanges object will be instantiated and called as such: # obj = SummaryRanges() # obj.addNum(value) # param_2 = obj.getIntervals()

2.4 复杂度分析

• 时间复杂度：
  • addNum(val)：$O(1)$，集合的插入操作时间复杂度为常数。
  • getIntervals()：$O(n \log n)$，其中 $n$ 为集合中数字的个数，主要时间消耗在排序上。
• 空间复杂度：$O(n)$，其中 $n$ 为添加的不同数字的个数。

三、进阶场景剖析：大量合并、区间稀少时怎么办？

原题给出了一条进阶问题：如果存在大量合并，并且与数据流的大小相比，不相交区间的数量很小，该怎么办？

先分析上面「集合 + 动态生成」方案在进阶场景下的瓶颈：

• getIntervals()每次都要对整个集合排序，复杂度为 $O(n \log n)$。
• 即便最终只有少数几个区间，只要数据量大（最多 $3 \times 10^4$ 次调用、$val$ 取值范围 $0 \le val \le 10^4$），排序成本依然可观。

可以推断，更贴合进阶要求的做法是让区间在addNum时增量维护，而不是在getIntervals时全量重建：

• 用有序集合（如 C++ 的std::set、Python 中借助sortedcontainers或二分查找维护的列表）保存当前的区间起点。
• addNum(val)时，通过二分查找定位val的前驱与后继区间，判断是否满足合并条件：
  • val落在某个已有区间[start, end]内部（start <= val <= end）：无需任何操作；
  • val == end + 1（紧邻左区间右侧）：扩展左区间的右端点；
  • val == next_start - 1（紧邻右区间左侧）：扩展右区间的左端点；
  • 两者同时成立：将左、右两个区间与val三者合并为一个新区间；
  • 都不成立：val作为孤立点形成新的单点区间[val, val]。
• getIntervals()直接返回有序集合中已维护的区间列表，复杂度为 $O(k)$，其中 $k$ 为区间个数。

在这种设计下，单次addNum的复杂度约为 $O(\log k)$（二分定位前驱后继）+ $O(1)$（合并），而getIntervals的复杂度与区间数量 $k$ 成正比。当区间数量 $k$ 远小于数据规模 $n$ 时，整体表现远优于「每次全量排序」。这也是本题标签中「二分查找、有序集合」的落点所在。

四、同类区间题对照：AlgoNote 中的区间问题家族

AlgoNote 的题解体系中，区间相关的题目形成了一条清晰的进阶路线，可帮助你横向巩固：

其中与本题设计思路最接近的是 0729. 我的日程安排表 I：同样是「设计」标签下的动态区间维护题，同样需要在每次插入时快速定位相邻区间。区别在于 0729 关注的是区间是否冲突（查询 + 判重），而 0352 关注的是区间如何合并（插入 + 归并），两者可以互为对照练习。

五、小结

回到本题，核心要点可以概括为三句话：

1. 正确性优先：addNum用集合 $O(1)$ 去重，getIntervals排序后按end + 1连续性切分区间，思路直白、易于验证，适合作为首版实现。
2. 性能进阶：当区间数量远小于数据量时，把「全量重建」改为「增量合并」——用有序集合配合二分查找维护区间，可把单次操作成本压到 $O(\log k)$。
3. 横向迁移：区间判定与合并的思维可以复用到汇总区间、合并区间、日程安排等一整套区间题，AlgoNote 的 0300-0399 题解目录 与 LeetCode 题解列表 中收录了大量同类题目供继续练习。

掌握「数据结构选型决定复杂度」这一设计题的核心命题，你就理解了本题乃至整个「设计 + 区间」类题目的通用解法框架。

• 教程
• 文档
• 知识库