【Hot 100 刷题计划】 LeetCode 128. 最长连续序列 | C++ 哈希表 O(N) 题解

LeetCode 128. 最长连续序列 | C Set 与哈希表 O(N) 双解法题解 题目描述题目级别中等给定一个未排序的整数数组nums找出数字连续的最长序列不要求序列元素在原数组中连续的长度。请你设计并实现时间复杂度为O(N)O(N)O(N)的算法解决此问题。示例输入nums [100, 4, 200, 1, 3, 2]输出4解释最长数字连续序列是[1, 2, 3, 4]。它的长度为 4。 解法一使用 Set 自动去重排序 (思路直观)最直观的想法是如果数组是有序的我们只需要遍历一遍就能找出最长连续序列。我们可以利用 C 中的set它底层基于红黑树不仅能自动去重还能自动排序。将所有元素塞入set后直接遍历寻找连续段即可。 C 代码实现classSolution{public:intlongestConsecutive(vectorintnums){if(nums.empty())return0;setintse;// 1. 将所有数字插入 set 中完成自动排序和去重for(inti0;inums.size();i){se.insert(nums[i]);}intres0,cnt1,fr-1,fl1;// 2. 遍历有序集合寻找连续序列for(autott:se){if(fl){fl0;res1;}elseif((tt-fr)1){// 如果当前数字和前一个数字连续cnt;resmax(res,cnt);}else{// 如果断开了重新开始计数cnt1;}frtt;// 更新前一个数字}returnres;}}; 解法二哈希表 智能跳过 (真正的 O(N) 面试最优解)要想把时间复杂度压榨到O(N)O(N)O(N)我们必须放弃排序借助哈希表unordered_set来实现O(1)O(1)O(1)的快速查找。核心破局点怎么找才不会超时如果我们把所有数字放入哈希表然后对每个数字都盲目地往后找比如对于 3 找 4,5,6对于 2 又找 3,4,5最坏情况下会退化成O(N2)O(N^2)O(N2)。优化的灵魂在于“只从序列的开头开始匹配”怎么判断一个数字是不是“序列的开头”很简单看它的前一个数字存不存在。如果 num - 1 在哈希表里说明 num 只是某个序列的中间节点直接跳过它如果 num - 1 不在哈希表里说明 num就是一个全新序列的开头。我们以它为起点放心地往后找 num1, num2…并记录长度。 进阶 C 代码实现classSolution{public:intlongestConsecutive(vectorintnums){// 将所有数字放入 unordered_set 中实现 O(1) 的查找并去重unordered_setinthash(nums.begin(),nums.end());intres0;// 遍历哈希表中的每一个数字for(intnum:hash){// 核心剪枝逻辑如果 num - 1 存在说明 num 不是序列起点直接跳过if(!hash.count(num-1)){// 此时 num 是一个新序列的起点intcurrentNumnum;intcurrentStreak1;// 顺藤摸瓜不断在哈希表中寻找下一个连续的数字while(hash.count(currentNum1)){currentNum1;currentStreak1;}// 更新全局最长序列长度resmax(res,currentStreak);}}returnres;}};