题目描述
思路解析
一句话答案：LeetCode 128 最长连续序列的 O(n) 解法是哈希集合加「只从起点数」：先把所有数放进集合获得 O(1) 查询，然后只对满足 x - 1 不在集合里的数 x（即某段连续序列的起点）向上逐个数 x+1、x+2 是否存在。每个数最多被访问两次，时间 O(n)、空间 O(n)，绕开了排序的 O(n log n)。
题目要什么，难点藏在哪
给一个无序整数数组，求「数值上连续」的最长一段有多长——比如 [100,4,200,1,3,2,5,6] 里最长的是 1、2、3、4、5、6，答案 6。元素在原数组里的位置无关紧要，只看数值。真正的难点是题目附加的硬要求：时间复杂度必须 O(n)，这一刀直接把「先排序再扫一遍」的 O(n log n) 常规做法排除在正解之外。
为什么不能排序，暴力又卡在哪
排序做法思路简单：排完序连续的数就挨在一起，扫一遍统计最长连击即可，但排序本身 O(n log n)，不满足题目要求。另一个直觉是对每个数 x 都试着往上数：x+1 在不在、x+2 在不在……判断「在不在」若靠遍历数组是 O(n) 一次，整体最坏 O(n²)；就算用哈希集合把查询降到 O(1)，「每个数都往上数一遍」在数组本身就是一长串连续数时，仍会把同一段序列重复数 n 遍，还是 O(n²)。
关键观察：只从每段序列的起点开始数
省掉重复的办法是给「往上数」加一个准入条件：只有当 x - 1 不在集合里时才从 x 起步。x - 1 不存在，说明 x 是某段连续序列的最左端（起点）；反过来，只要 x - 1 存在，x 就处在别人的序列中段，从它数出来的一定是条被截短的重复子段，不数也罢。
这个小判断改变了整体的账：每段连续序列只会被它唯一的起点完整数一遍，序列内部的其他数只在准入判断时被看一眼。所有段加起来，每个元素最多被访问常数次，总时间稳稳落在 O(n)。
哈希集合在这里干了两件事
第一件是去重：set(nums) 把重复元素合并，重复的数既不该让序列变长，也会干扰起点判断，入集合时顺手解决。第二件是 O(1) 查询：无论是「x - 1 在不在」的起点判断，还是往上数时「cur + 1 在不在」的续链判断，都是一次哈希查找。整套算法就是「一次建集合 + 对每个集合元素做常数次查询」，没有任何排序或嵌套扫描。
复杂度怎么数出来，哪里容易翻车
时间 O(n)：建集合 O(n)；遍历集合时，非起点的数只花一次判断，起点的数把自己那段数完，每个元素作为「被数到的对象」恰好一次，两项相加仍是线性。空间 O(n)：集合存全部去重后的数。
最容易翻车的一处是漏掉「只从起点数」这个限制——代码能跑、答案也对，但复杂度退化成 O(n²)，大数据量直接超时，面试官追问复杂度时也答不上来。其次是遍历对象：第二遍循环应遍历去重后的集合而不是原数组，否则重复元素会让同一个起点被反复数。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
核心：先把所有数放进哈希集合（去重 + O(1) 查询）。再只从「起点」起步往上数——一个数 x 是起点当且仅当 x-1 不在集合里。这样每个数只会被数到一次，总共 O(n)。
1. 入集合 nums[0]=100：第一遍：把 nums[0] = 100 放进哈希集合（橙色）。集合会自动去重，并支持 O(1) 判断某个数在不在。放完所有数后再开始数连续。
2. 入集合 nums[1]=4：第一遍：把 nums[1] = 4 放进哈希集合（橙色）。集合会自动去重，并支持 O(1) 判断某个数在不在。放完所有数后再开始数连续。
3. 入集合 nums[2]=200：第一遍：把 nums[2] = 200 放进哈希集合（橙色）。集合会自动去重，并支持 O(1) 判断某个数在不在。放完所有数后再开始数连续。
4. 入集合 nums[3]=1：第一遍：把 nums[3] = 1 放进哈希集合（橙色）。集合会自动去重，并支持 O(1) 判断某个数在不在。放完所有数后再开始数连续。
5. 入集合 nums[4]=3：第一遍：把 nums[4] = 3 放进哈希集合（橙色）。集合会自动去重，并支持 O(1) 判断某个数在不在。放完所有数后再开始数连续。
6. 入集合 nums[5]=2：第一遍：把 nums[5] = 2 放进哈希集合（橙色）。集合会自动去重，并支持 O(1) 判断某个数在不在。放完所有数后再开始数连续。
7. 入集合 nums[6]=5：第一遍：把 nums[6] = 5 放进哈希集合（橙色）。集合会自动去重，并支持 O(1) 判断某个数在不在。放完所有数后再开始数连续。
8. 入集合 nums[7]=6：第一遍：把 nums[7] = 6 放进哈希集合（橙色）。集合会自动去重，并支持 O(1) 判断某个数在不在。放完所有数后再开始数连续。
9. 起点 100（99不在集合）：考察 100：前一个数 99 不在集合里，所以 100 是一段连续序列的起点（绿色）。从它开始往上数：当前序列 = [100]，当前长度 cur_len = 1。
10. 100 这段到 100 停：101 不在集合里，从 100 起的这段连续序列到此结束：100，长度 1。这段里的每个数都被标成已数过（绿/灰），后面不会再从它们重复往上数。
11. 跳过 4（非起点）：考察 4：它的前一个数 3 在集合里，说明 4 不是某段连续序列的起点（3 才是更靠前的起点）。直接跳过，绝不从这里往上数——这正是避免重复、保证 O(n) 的关键。
12. 起点 200（199不在集合）：考察 200：前一个数 199 不在集合里，所以 200 是一段连续序列的起点（绿色）。从它开始往上数：当前序列 = [200]，当前长度 cur_len = 1。
13. 200 这段到 200 停：201 不在集合里，从 200 起的这段连续序列到此结束：200，长度 1。这段里的每个数都被标成已数过（绿/灰），后面不会再从它们重复往上数。
14. 起点 1（0不在集合）：考察 1：前一个数 0 不在集合里，所以 1 是一段连续序列的起点（绿色）。从它开始往上数：当前序列 = [1]，当前长度 cur_len = 1。
15. 延伸到 2（长度 2）：往上看 2：它在集合里，所以这段连续序列延伸到 2（绿色一整段 1→2）。当前长度 cur_len = 2，更新最长 longest = 2。
16. 延伸到 3（长度 3）：往上看 3：它在集合里，所以这段连续序列延伸到 3（绿色一整段 1→2→3）。当前长度 cur_len = 3，更新最长 longest = 3。
17. 延伸到 4（长度 4）：往上看 4：它在集合里，所以这段连续序列延伸到 4（绿色一整段 1→2→3→4）。当前长度 cur_len = 4，更新最长 longest = 4。
18. 延伸到 5（长度 5）：往上看 5：它在集合里，所以这段连续序列延伸到 5（绿色一整段 1→2→3→4→5）。当前长度 cur_len = 5，更新最长 longest = 5。
19. 延伸到 6（长度 6）：往上看 6：它在集合里，所以这段连续序列延伸到 6（绿色一整段 1→2→3→4→5→6）。当前长度 cur_len = 6，更新最长 longest = 6。
20. 1 这段到 6 停：7 不在集合里，从 1 起的这段连续序列到此结束：1→2→3→4→5→6，长度 6。这段里的每个数都被标成已数过（绿/灰），后面不会再从它们重复往上数。
21. 跳过 3（非起点）：考察 3：它的前一个数 2 在集合里，说明 3 不是某段连续序列的起点（2 才是更靠前的起点）。直接跳过，绝不从这里往上数——这正是避免重复、保证 O(n) 的关键。
22. 跳过 2（非起点）：考察 2：它的前一个数 1 在集合里，说明 2 不是某段连续序列的起点（1 才是更靠前的起点）。直接跳过，绝不从这里往上数——这正是避免重复、保证 O(n) 的关键。
23. 跳过 5（非起点）：考察 5：它的前一个数 4 在集合里，说明 5 不是某段连续序列的起点（4 才是更靠前的起点）。直接跳过，绝不从这里往上数——这正是避免重复、保证 O(n) 的关键。
24. 跳过 6（非起点）：考察 6：它的前一个数 5 在集合里，说明 6 不是某段连续序列的起点（5 才是更靠前的起点）。直接跳过，绝不从这里往上数——这正是避免重复、保证 O(n) 的关键。
25. 扫描结束：所有起点都处理完了。最长的一段连续序列是 1→2→3→4→5→6（绿色），长度 6。整个过程：每个数入一次集合、每段只从起点往上数一次，总共 O(n)。
26. 返回答案：返回 longest = 6。注意 100 和 200 各自只是长度 1 的孤立序列，真正最长的是 1 到 6 这一段。
记住这题的骨架：哈希集合负责 O(1) 查询，「只从起点起步」这个限制让总数数次数等于元素个数，把朴素 O(n²) 压成 O(n)。
参考代码
class Solution: def longestConsecutive(self, nums): num_set = set(nums) longest = 0 for x in num_set: if x - 1 not in num_set: cur, length = x, 1 while cur + 1 in num_set: cur += 1 length += 1 longest = max(longest, length) return longest复杂度
- 时间复杂度：O(n)，每个数最多被「往上数」访问一次
- 空间复杂度：O(n)，哈希集合存全部数
易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
多数元素
LeetCode 169 · 简单 · 沿着 数组 & 哈希 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题