一、题目解析
1.1 题目描述
给定一个未排序的整数数组 nums，找出数字连续的最长序列的长度。这里的连续指数值上连续，比如 1、2、3、4，与它们在数组中的先后位置无关。题目要求算法的时间复杂度为 O(n)。
O(n) 这个限制把排序挡在门外。排序后扫一遍相邻元素差值是最自然的做法，但那是 O(n log n)。要压到线性，只能借助哈希表把「某个数在不在」这个查询变成 O(1)。
1.2 示例
输入：nums = [100, 4, 200, 1, 3, 2]
输出：4
解释：最长的连续序列是 1, 2, 3, 4，长度为 4。100 和 200 各自孤立，谁也接不上。
输入：nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
输出：9
解释：0 出现了两次，重复元素不会让序列变长，连续段是 0 到 8。
二、思路分析
2.1 先去重
把所有数丢进 HashSet。这一步做了两件事：一是 contains 变成 O(1)，可以随时问「比它小 1 的数存在吗」；二是消掉重复元素。
2.2 只从起点开始计数
去重之后，一个朴素的想法是：对每个元素都往后延伸，能延伸多远就是多长。这个做法的答案是对的，但代价很大。设集合里有 1, 2, 3, ..., n 这条完整的链，从 1 出发走 n 步，从 2 出发走 n-1 步，从 3 出发走 n-2 步，加起来是 O(n²)。同一条链被重复统计了 n 遍。
改进的关键是让每条连续段只被统计一次，并且从它的头部统计。判断条件很简单：如果 item - 1 不在集合里，说明 item 前面接不上东西，它就是某条连续段的起点。只有起点才有资格进入 while 循环向后延伸；item - 1 存在的元素直接跳过，因为它所在的链迟早会被链头的起点覆盖到。
回到 [100, 4, 200, 1, 3, 2]，集合里满足起点条件的只有 1、100、200 三个数。2、3、4 都因为前驱存在而被跳过，一次都不进 while。
2.3 复杂度
外层 for 遍历集合是 n 次，每次做一趟 contains(item - 1) 判断，这部分总共 O(n)。
内层 while 看上去嵌套在 for 里，但它跑的次数与外层是解耦的。while 每前进一步就走过一个新元素，而每个元素只可能属于唯一一条连续段，也只会被这条段的起点走到一次。把所有起点的 while 步数加起来，不超过集合里元素的总数，还是 O(n)。
换个角度看：每个元素最多被访问两次，一次是外层 for 对它做起点判定，一次是被某个起点的 while 延伸经过。两次相加仍是常数，所以总时间 O(n)。
三、代码实现
class Solution { public int longestConsecutive(int[] nums) { // 哈希集合：去掉重复元素，同时把「某个数是否存在」的查询降到 O(1) Set<Integer> set = new HashSet<>(); for (int i = 0; i < nums.length; i++) { set.add(nums[i]); } int ans = 0; // 遍历去重后的集合，而不是原数组，避免重复元素带来的无效延伸 for (int item : set) { // 起点判定：item - 1 不在集合中，说明 item 前面接不上，它是一条连续段的头 // 有前驱的元素直接跳过，它所在的链会由链头的起点统计 if (!set.contains(item - 1)) { // 从起点开始，长度至少为 1 int len = 1; int cur = item; // 逐个向后延伸，能接上就把长度加一 while (set.contains(cur + 1)) { cur++; len++; } // 记录目前见过的最长连续段 ans = Math.max(ans, len); } } return ans; }}四、图解过程
以 nums = [100, 4, 200, 1, 3, 2] 为例。
第一步，全部入集合，得到 {1, 2, 3, 4, 100, 200}，本例没有重复元素，规模保持 6。
第二步，对集合里每个元素做起点判定：
1：集合中没有0，是起点。2：集合中有1，跳过。3：集合中有2，跳过。4：集合中有3，跳过。100：集合中没有99，是起点。200：集合中没有199，是起点。
六个元素里只有 1、100、200 三个进入了 while 循环。
第三步，对三个起点分别延伸：
从 1 出发，len = 1，cur = 1。集合有 2，cur 变 2、len 变 2；集合有 3，cur 变 3、len 变 3；集合有 4，cur 变 4、len 变 4；集合没有 5，循环结束。得到序列 1, 2, 3, 4，长度 4，ans 更新为 4。
从 100 出发，集合里没有 101，while 一次都不执行，长度停在 1，ans 保持 4。
从 200 出发，集合里没有 201，同样长度 1，ans 依旧是 4。
整个过程里，while 循环一共只走了 3 步（分别接上 2、3、4），没有任何元素被两条不同的链重复延伸。最终返回 4。
五、复杂度分析
时间复杂度 O(n)。建集合是 n 次 add，遍历集合做起点判定是 n 次 contains，所有 while 的步数加起来不超过集合大小。三部分都是线性的，哈希操作平均 O(1)。
空间复杂度 O(n)。额外空间只有那个 HashSet，最坏情况下数组里没有重复元素，集合要装下全部 n 个数。
本文由 AgentPlanFlow 生成