题目描述
思路解析动画文字版
记住「看下一个是不是 +1:是就延伸,不是就收尾」,下面每帧都在套它。
扫到 0(紫色),绿色是当前正在生长的区间。看它的下一个 1 是不是正好等于 0+1=1?
1 正好是 0+1,连续!绿色区间往右长一格,包进 1,起点仍是 0。继续往后看。
扫到 1(紫色),绿色是当前正在生长的区间。看它的下一个 2 是不是正好等于 1+1=2?
2 正好是 1+1,连续!绿色区间往右长一格,包进 2,起点仍是 0。继续往后看。
扫到 2(紫色),绿色是当前正在生长的区间。看它的下一个 4 是不是正好等于 2+1=3?
4 不等于 2+1,断开。这段从 0 连到 2,输出 "0->2"。这段变蓝表示已汇总,下一个数另起一段。
扫到 4(紫色),绿色是当前正在生长的区间。看它的下一个 5 是不是正好等于 4+1=5?
5 正好是 4+1,连续!绿色区间往右长一格,包进 5,起点仍是 4。继续往后看。
扫到 5(紫色),绿色是当前正在生长的区间。看它的下一个 7 是不是正好等于 5+1=6?
7 不等于 5+1,断开。这段从 4 连到 5,输出 "4->5"。这段变蓝表示已汇总,下一个数另起一段。
扫到 7(紫色),绿色是当前正在生长的区间。看它的下一个 8 是不是正好等于 7+1=8?
8 正好是 7+1,连续!绿色区间往右长一格,包进 8,起点仍是 7。继续往后看。
扫到 8(紫色),绿色是当前正在生长的区间。看它的下一个 9 是不是正好等于 8+1=9?
9 正好是 8+1,连续!绿色区间往右长一格,包进 9,起点仍是 7。继续往后看。
扫到 9(紫色),绿色是当前正在生长的区间。看它的下一个 11 是不是正好等于 9+1=10?
11 不等于 9+1,断开。这段从 7 连到 9,输出 "7->9"。这段变蓝表示已汇总,下一个数另起一段。
扫到 11(紫色),绿色是当前正在生长的区间。看它的下一个 13 是不是正好等于 11+1=12?
13 不等于 11+1,断开。这段只有 11 一个数,落单,输出 "11"。这段变蓝表示已汇总,下一个数另起一段。
扫到最后一个 13(紫色)。后面没有数了,当前这段绿色区间必须收尾。
到末尾。这段只有 13 一个数,落单,输出 "13"。这段变蓝表示已汇总,下一个数另起一段。
扫完全程,整个数组被切成 5 段连续区间:0->2、4->5、7->9、11、13。一遍扫描、不回头,就把所有区间汇总好了。
边界先想清:空、单个、全不连续。
面试追问围绕「分段断点判断」与前置假设(升序无重复)。
参考代码
from typing import Listclass Solution: def summaryRanges(self, nums: List[int]) -> List[str]: ans = [] i = 0 while i < len(nums): start = nums[i] while i + 1 < len(nums) and nums[i + 1] == nums[i] + 1: i += 1 if start == nums[i]: ans.append(str(start)) else: ans.append(f"{start}->{nums[i]}") i += 1 return ans复杂度
- 时间:O(n),每个元素只被看一次
- 空间:O(1),不算输出,只用起点等常数变量
易错点
面试追问把动画讲成自己的话
追问为什么用「比下一个」而不是「比上一个」来分段?
追问如果数组可能有重复或不保证升序怎么办?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题