【LeetCode 128】最长连续序列C 详细题解LeetCode hot100 题目描述给定一个未排序的整数数组nums找出数字连续的最长序列不要求序列元素在原数组中连续的长度。要求设计并实现时间复杂度为O(n)的算法。示例 1输入nums [100,4,200,1,3,2]输出4解释最长数字连续序列是 [1, 2, 3, 4]长度为 4。 核心思路这道题最巧妙的地方在于不排序、不暴力遍历我们用unordered_set哈希集合来做1. 去重 快速查找把所有数字丢进集合里好处有两个自动去重重复数字不影响连续长度O(1) 查找2. 找「起点」只算一次规则如果一个数字num它前面的数字num-1不存在那它就是连续序列的起点。是起点往后一直数统计长度。不是起点直接跳过不做重复计算3. 比较所有长度取最大值每找到一个起点就算出这一段连续序列的长度最后保留最大的那个✅ 最终 AC 代码可直接提交classSolution{public:intlongestConsecutive(vectorintnums){// 1. 创建哈希集合用于去重和快速查找unordered_setints;intmaxcount0;// 记录最长长度// 2. 把数组所有数字存入集合自动去重for(intnum:nums){s.insert(num);}// 3. 遍历集合里的每一个数字每个数字只看一次for(intnum:s){// 判断如果 num-1 不存在说明 num 是起点if(!s.count(num-1)){intcount1;// 当前序列长度起点本身算1个intcurnum;// 用cur往后跑不修改原num// 4. 从起点开始一直往后找连续数字while(s.count(cur1)){count;// 长度1cur;// 当前数字往后走}// 5. 更新最大值maxcountmax(count,maxcount);}}returnmaxcount;// 返回结果}}; 逐行代码超详细讲解1. 定义集合unordered_setints;作用存放所有数字自动去重查找速度极快。2. 存入所有数字for(intnum:nums){s.insert(num);}把数组里的数全部放进集合。重复数字会被自动过滤只留一个。3. 遍历集合for(intnum:s)遍历集合而不是原数组避免重复计算保证 O(n) 效率。4. 判断是不是起点if(!s.count(num-1))s.count(x)判断 x在不在集合里!s.count(num-1)前面没有数字 → 我是起点5. 向后统计长度intcount1;intcurnum;while(s.count(cur1)){count;cur;}cur替身变量从起点开始往后跑。count记录当前连续序列有多长。6. 更新最大值maxcountmax(count,maxcount);每次算完一段连续序列就和当前最大值比较保留更大的。 运行过程演示数组[100,4,200,1,3,2]存入集合后{100,4,200,1,3,2}10099 不存在 → 起点 → 长度 143 存在 → 跳过200199 不存在 → 起点 → 长度 110 不存在 →起点找 2 → 有找 3 → 有找 4 → 有长度 432 存在 → 跳过21 存在 → 跳过最终最长长度4