做算法题最爽的一刻就是发现一个看起来要折腾半天的题目最后只需要一趟循环就能干净利落地解决。LeetCode 228 汇总区间Summary Ranges就是这么一道题给你一个已经升序排列、不含重复数字的整数数组把连续的数字合并成区间字符串——单个数字输出它自己连续的一段输出起点-终点。比如输入 [0,1,2,4,5,7]要返回 [0-2,4-5,7]输入 [0,2,3,4,6,8,9]要返回 [0,2-4,6,8-9]。逻辑本身不复杂但用 C 语言写的时候很多第一次刷题的人会在函数签名、内存分配、字符串格式化这些地方卡住反而算法逻辑是最简单的部分。这篇会把思路演进从头捋一遍先讲最直觉的做法再一步步收敛到 O(n) 一趟扫描然后给出能直接过题的 C 代码配上图解和踩坑心得。适合刚开始刷题、尤其是用 C 语言刷题的同学已经会做的也可以看看边界处理和内存细节这些地方翻车率相当高。1. 题目到底在考什么1.1 一句话的人话版本先看题面给定一个已经排好序的唯一整数数组要求返回最小区间列表这些区间要恰好覆盖数组中的所有数字。如果 a 和 b 不相等就输出 a-b如果相等就只输出 a。人话就是数组已经帮你排好序了也没有重复你要做的事就是找连续块。什么叫连续块相邻两个数相差正好是 1。比如 1、2、3 是一个块3 和 5 之间差 2所以 5 得另起一个块。每个块转成一个字符串最后把这些字符串按顺序放进一个指针数组返回。官方给了两个例子nums [0,1,2,4,5,7] → [0-2,4-5,7]nums [0,2,3,4,6,8,9] → [0,2-4,6,8-9]这里有个容易误解的地方最小区间列表不是说你要用最少的字符串而是说每个块的表示要最紧凑。比如 [1,2,3] 你不能拆成多个小区间必须合并成 1-3因为题目要求覆盖所有数字且列表要最小。换句话说就是贪心地合并所有能合并的连续段。1.2 三个藏在边界里的坑这种题最容易翻车的不是主逻辑而是边界。第一个是空数组。numsSize 为 0 时返回什么答案是空列表*returnSize 置 0返回 NULL 就可以。第二个是单元素数组。比如 [-1]a b输出字符串 -1 而不是 -1--1。很多初学者把相等情况漏掉直接走了带箭头的分支。第三个是负数和 INT_MAX。负数在字符串格式化时比正数多一个负号长度计算要用对方法而 INT_MAX 附近做 1 运算要当心溢出。后面我会专门讲这几处。记住这三个坑写代码的时候心里就有谱了。2. 思路演进从暴力 O(n²) 到一遍扫描 O(n)2.1 最直觉的暴力做法每个起点都往后数看到这道题第一反应是从每个元素出发往后一个个数数到连续断掉为止。写出来大概是拿一个游标 j 从 i 开始只要 nums[j1] nums[j] 1j 就一直往后走走出来一段再让 i j 1 继续下一段。这个想法其实已经接近正解了。它的核心操作是比较相邻两个数是否差 1因为数组有序且无重复差 1 是连续段的充要条件。你不需要关心更远的数——2 和 4 之间隔了个 3不连续2 和 6 之间隔了一串数也不连续。判断相邻就足够了。2.2 为什么暴力会做无用功如果你在暴力版里对每个 i 都重新往后扫到尽头会发现有的元素被反复看了好几遍。比如 [0,1,2,3,4,5] 这种长连续段从 0 扫到 5 得到一段然后又从 1 扫到 5、从 2 扫到 5……每一段都在重复遍历共同的后缀总工作量就变成 O(n²) 了。这道题真正的关键不是要不要往后数而是每个元素最多被检查几次。答案是最多两次。一次是作为某段起点被读取一次是作为连续关系里的当前元素被推进。只要保证每个元素只被扫过一遍就定位到所属区间就是最优的。2.3 核心演进用两个指针把区间踩出来我们把正解叫双指针扫描一个指针负责记住当前段的起点 start另一个指针 i 负责探路把连续的数字一路踩过去。当 i 停在某个位置发现下一个数接不上了那 start 到 i 这段就是一个完整区间生成字符串然后 start 更新为下一个数继续。注意这里的 start 并不是严格意义上的快慢指针它更像一个标记记录当前这一段的开头在哪。理解这一点就够了你只需要维护当前段的开始和当前段的下一个待检查位置两个信息就可以一次遍历完成所有合并。三种做法对比看得很清楚做法核心操作时间复杂度空间复杂度不含结果评价暴力嵌套每个起点都往后扫到底O(n²)O(1)直观但冗余二分找段尾对每个起点二分找最后连续位置O(n log n)O(1)可行但没必要一趟扫描相邻判断推进 iO(n)O(1)最优推荐2.4 为什么一趟扫描就是最优解内层 while 每推进一步i 就永久前进一格外层循环不会回头所以最多 2n 次比较时间复杂度 O(n)。能不能用二分找段尾可以每次二分找nums[mid] - nums[start] mid - start成立的最大位置但总复杂度变成 O(n log n)反而更慢。因为这里判断连续的代价是 O(1)线性已经是最优了。空间上除了输出本身你只需要几个变量但加上结果的字符串存储最坏情况所有元素都不连续要 O(n) 个字符串这也是输出本身的大小没法省。3. C语言完整实现从函数签名到内存分配3.1 先看懂 char** 和 returnSizeLeetCode 给的 C 接口是这样char** summaryRanges(int* nums, int numsSize, int* returnSize);它要求你返回一个 char**也就是字符串指针数组每个字符串是你生成好的区间通过 *returnSize 告诉调用方一共有几个区间所有指针和字符串都要用 malloc 分配因为调用方会负责释放。很多新手栽在 returnSize 上只改了局部变量没写回 *returnSize或者忘了初始化。这些都会导致调用方拿到错误的大小轻则输出少一段重则内存访问越界。我自己调试时就干过这事函数里算得好好的出来一看 returnSize 是一堆随机数就是因为忘了初始化。3.2 主循环一前一后两个变量的妙用外层 while (i numsSize)每次循环开始前记录 start nums[i]然后内层 while 把 i 推到当前段的末尾while (i 1 numsSize nums[i 1] nums[i] 1) { i; }跳出内层循环时nums[i] 就是段尾。这里有个细节跳出后不能直接 i要先根据 start 和 nums[i] 生成字符串最后再 i。如果把 i 放在生成字符串之前段尾信息就丢了。这个顺序逻辑上很像先收割再前进start 是这段的起点nums[i] 是这段的终点收割完这一段的字符串i 才能继续往下一段走。3.3 字符串安全构造先量长度再分配在 C 里生成 0-2 或者 7 这种动态字符串最稳的方式是先调 snprintf(NULL, 0, ...) 算出需要多少字符再 malloc 对应大小最后 sprintf 写入int len snprintf(NULL, 0, %d-%d, start, end); char* s (char*)malloc(len 1); sprintf(s, %d-%d, start, end);snprintf 返回的是除去 \0 之外的字符数所以 malloc 要加 1。很多人图省事直接 char buf[32]; sprintf(buf, ...)本题这样写通常也能过但一旦格式模板复杂固定缓冲区就有溢出风险。用 snprintf 量长度是更稳的习惯尤其是负数长度可变别手算位数。3.4 可直接过题的完整代码#include stdio.h #include stdlib.h char* makeRange(int start, int end) { int len; char* s; if (start end) { len snprintf(NULL, 0, %d, start); s (char*)malloc(len 1); sprintf(s, %d, start); } else { len snprintf(NULL, 0, %d-%d, start, end); s (char*)malloc(len 1); sprintf(s, %d-%d, start, end); } return s; } char** summaryRanges(int* nums, int numsSize, int* returnSize) { *returnSize 0; if (numsSize 0) { return NULL; } char** res (char**)malloc(sizeof(char*) * numsSize); int i 0; while (i numsSize) { int start nums[i]; while (i 1 numsSize nums[i 1] nums[i] 1) { i; } if (start nums[i]) { res[*returnSize] makeRange(start, start); } else { res[*returnSize] makeRange(start, nums[i]); } (*returnSize); i; } return res; }这版代码在判题环境的 C 环境里可以直接过。空数组返回 NULL*returnSize 为 0正常情况返回指针数组。makeRange 把单个数字和区间两个分支拆开逻辑清晰也方便单独测试。4. 图解区间一步步合并的全过程4.1 三个区间怎么被依次找出以 [0,1,2,4,5,7] 为例整个过程分三步第 1 段start 0 nums: [0, 1, 2, 4, 5, 7] ↑ i0 比较 nums[1]nums[0]1 → 11i1 比较 nums[2]nums[1]1 → 22i2 比较 nums[3]nums[2]1 → 43停 区间 [0,2] → 0-2 第 2 段start 4 nums: [0, 1, 2, 4, 5, 7] ↑ i3 比较 nums[4]nums[3]1 → 55i4 比较 nums[5]nums[4]1 → 76停 区间 [4,5] → 4-5 第 3 段start 7 nums: [0, 1, 2, 4, 5, 7] ↑ i5 i16不满足 i1 6直接停 区间 [7,7] → 7看完这个过程你会发现内层 while 其实就是沿着连续的数字一路踩过去直到踩空为止。每一步都只关心相邻两个数根本不需要回头看。4.2 字符串拼接与内存布局生成 4-5 时sprintf 会把三部分拼进分配好的内存4 - 5 \0snprintf(NULL, 0, %d-%d, 4, 5) 返回 4字符 4、-、、5所以 malloc 5 字节最后一位放 \0。而 7 只需要 2 字节负数 -1 是 3 字节。这些都由 snprintf 自动帮你算好。返回的指针数组大致长这样char** res res[0] ── 0-2\0 res[1] ── 4-5\0 res[2] ── 7\0 *returnSize 3res 是外层的大数组每个元素是一个 char*指向单独 malloc 出来的一小段字符串。释放的时候两层都要 free先释放每个字符串再释放 res 本身。4.3 四种边界情况的图解空数组 []没有循环可走*returnSize 置 0返回 NULL。单元素 [5]外层循环进来start5内层条件失败i11 不成立区间 [5,5]走相等分支生成 5。全是独立数 [1,3,5]每个元素各成一段结果 [1,3,5]对应最坏空间情况。全连续 [1,2,3]一段走到底结果 [1-3]只有一条字符串。用上面的代码跑一遍这四个输出都符合预期。5. 踩坑实录C语言版最容易翻车的四个点5.1 i 自增位置导致区间错位最容易踩的坑是内层 while 的写法。有人会改成 do-while或者错误地把 i 放在生成字符串之后结果要么死循环要么区间起点被跳过。我自己调试时遇到过一次在生成字符串前先写了 i导致 start 和 nums[i] 错位输出变成了 [0-1,3-4,6] 这种奇怪结果。定位方法很简单在每个区间开头打印 start 和当前 i对比一下就明白了。打印日志永远比干瞪眼快。5.2 本地测试的内存泄漏与野指针判题环境会接管并释放你返回的字符串但本地自测时一定要记得 free。可以写个简单测试函数for (int j 0; j *returnSize; j) { printf(%s\n, res[j]); free(res[j]); } free(res);另外注意不要试图返回栈上分配的数组比如char resLocal[100][32]然后返回它这种数组在函数返回后就失效了属于未定义行为。必须用 malloc。这个坑在本地跑还好一旦接入标准评判环境表现就是随机崩溃或者输出乱码。5.3 空数组与返回值的处理如果 numsSize 0malloc(sizeof(char*) * 0)的行为在不同编译器上不完全一致而且即使分配成功你也没有任何字符串要写那就不如直接返回 NULL把 *returnSize 设为 0语义干净。这个分支要放在函数开头别等循环自然结束否则可能出现奇怪的空指针解引用。5.4 INT_MAX 溢出隐患与防御写法内层条件写了nums[i 1] nums[i] 1如果 nums[i] 是 INT_MAXnums[i] 1 会溢成负数吗答案是在合法输入下不会执行到这。因为数组有序且无重复INT_MAX 一定是最后一个元素而i 1 numsSize这个条件会先短路nums[i] 1根本不会被求值。所以这段代码是安全的。但如果你觉得不放心可以写成更防御的版本while (i 1 numsSize (long long)nums[i 1] - nums[i] 1) { i; }用 long long 做差彻底避免任何整数溢出争议。这条技巧在面试里主动说出来会显得你很懂 C 的边界也确实是实际工程里值得养成的习惯。常见问题速查症状原因解法输出多一段或少一段returnSize 没写回或 i 自增位置错生成字符串后置 (*returnSize)再 i字符串内容乱码固定缓冲区太小导致越界用 snprintf(NULL,0,...) 量长度再分配本地运行崩溃返回了栈上数组或忘 malloc所有返回对象都用 malloc结果全是空串snprintf 返回值理解错误返回值不含 \0malloc 要加 16. 复杂度与同类题的通用套路6.1 时间与空间复杂度分析时间复杂度 O(n)每个元素最多被访问两次一次作为段内元素被推进一次作为段尾被读取。空间复杂度不含结果的话是 O(1)只用了几个变量含结果不超过 O(n)因为最坏情况每个元素生成一个字符串。这已经是理论最优因为每个元素至少要读一次每个区间字符串至少要构造一次。6.2 区间类题目的通用骨架汇总区间属于区间合并家族。这类题的通用套路是先排序如果没排序然后维护一个当前区间依次判断下一个元素或者下一个区间能不能续进来。判断标准往往是是否连续或是否重叠。掌握了 228 题再去看合并区间、插入区间这类题会发现主循环结构非常相似区别只在合并条件和区间表示方式。用一张表概括这个家族题目类型判断条件输出形式汇总区间相邻差 1区间字符串列表合并区间区间是否重叠合并后的区间对插入区间新区间与已有区间是否重叠插入合并后的区间对6.3 乱序数组和重复数字的变体题目特意保证有序如果把条件放宽成乱序数组就得先排序再走同样的流程复杂度 O(n log n)。另外如果允许重复数字判断连续时要把重复当成不连续来处理或者先去重再合并。这些变体在面试里经常被追问本质上都在考察相邻元素关系这个核心点理解了 228 题的扫描骨架变体也就只是加个预处理的事。最后说点我自己的体会。这道题我第一次刷的时候算法逻辑五分钟就想通了结果在字符串格式化上卡了快半小时——当时用的是固定数组加 sprintf遇到负数没算对长度越界把结果整个搞乱了。后来养成习惯凡是动态字符串一律先用 snprintf 量长度再分配这类问题就再没出现过。228 题看起来简单但它非常适合用来练 C 语言的两项基本功指针数组的分配与释放、动态字符串的安全构造。把这两项练熟了后面做更复杂的题目会省很多事。如果你刷完这题还有余力建议把合并区间、插入区间一起做一遍你会发现它们的骨架其实长得一模一样。
