最长连续序列
Longest Consecutive Sequence
给定未排序的整数数组，求数字连续的最长序列的长度。序列不要求在数组中相邻，但要求 O(n)。
在力扣中练习题目描述
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9
示例 3：
输入：nums = [1,0,1,2] 输出：3
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109
解题思路
哈希集合 · 只从起点数
把「查找」降到 O(1)，再让每段序列只被数一次
先排序也能找连续段，但要付出 O(n log n)。哈希集合能去重并查询某个值是否存在，关键是避免从一段里的每一个数重新往后数。
自拟主例 [8,2,5,3,2,9,4,12] 有重复值，也有多个互不相连的段。去重后最长的是 2,3,4,5，长度为 4；8,9 和单独的 12 不会与它拼起来。
从起点 8 扩展到 9，长度 2，best=2。
- best
- 2
只有 x-1 不存在时，x 才是起点。 从这个起点递增到整段末尾，更新最长长度。其他段内元素只做一次前驱判断，不再展开。图中集合排序只为方便读图，代码不依赖集合的迭代顺序；从哪个起点先开始都得到同一个答案。
易错点
- 不判断起点（不查 x - 1），答案虽然对，但最坏情况会退化成 O(n²)。
- 长度写成 y - x，少了 1；或者内层数完忘了更新 best。
- best 初始化为 1 却没处理空数组，nums = [] 时会返回 1（正确答案是 0）。
排序 · 一次扫描
排好序后，连续的数一定挨在一起
结果正确，但 O(n log n) 不满足本题要求的 O(n)；仅作排序思路对照，提交优先用主解法。
如果面试官不卡 O(n)，最省事的做法是排序后扫一遍：相邻元素差 1 就 ++cur，差更多就 cur = 1 重新计数，相等则是重复元素，跳过。
它把「连续」这个关系变成了相邻位置的比较，所以不需要哈希表，排序还会使用 O(log n) 的递归栈。代价是排序的 O(n log n)，以及会修改输入数组（如果不想改，先拷贝一份）。
这段代码有一个很容易踩的坑：重复元素必须先跳过再判差。否则 [1,2,2,3] 里第二个 2 会让 nums[i] - nums[i-1] == 0 走进 else 分支，把 cur 重置成 1。
两种写法对比着记：排序版思路直白，哈希版满足题目的 O(n) 要求。
- 1空数组直接返回 0。
- 2排序整个数组。
- 3从第二个元素开始扫描：相等就跳过（重复）。
- 4差 1 则 cur 加一，否则 cur 重置为 1，并随时更新 best。
易错点
- 把重复元素的判断放到 else 分支里，cur 会被错误重置。
- 忘记空数组，nums[0] 越界。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
nums = [8, 2, 5, 3, 2, 9, 4, 12]用集合去重，best 从 0 开始。集合的遍历顺序不影响答案。
查看 C++ 代码
延伸阅读
- 「只从起点展开」是一种通用剪枝：先判断自己是不是最小/最左/最起点，再决定要不要花力气展开。
- 数据范围小时也可以用并查集，把相邻的数合并，思路与哈希集合一致，只是合并时要靠哈希表找邻居。
- 题目只要长度；如果要输出具体序列，在更新 best 时顺手把起点和终点记下来即可。