【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(vector<int>&nums){if(nums.empty())return0;set<int>se;// 1. 将所有数字插入 set 中，完成自动排序和去重for(inti=0;i<nums.size();i++){se.insert(nums[i]);}intres=0,cnt=1,fr=-1,fl=1;// 2. 遍历有序集合，寻找连续序列for(autott:se){if(fl){fl=0;res=1;}elseif((tt-fr)==1){// 如果当前数字和前一个数字连续cnt++;res=max(res,cnt);}else{// 如果断开了，重新开始计数cnt=1;}fr=tt;// 更新前一个数字}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
  就是一个全新序列的开头。我们以它为起点，放心地往后找 num+1, num+2…，并记录长度。

💻 进阶 C++ 代码实现

classSolution{public:intlongestConsecutive(vector<int>&nums){// 将所有数字放入 unordered_set 中，实现 O(1) 的查找并去重unordered_set<int>hash(nums.begin(),nums.end());intres=0;// 遍历哈希表中的每一个数字for(intnum:hash){// 核心剪枝逻辑：如果 num - 1 存在，说明 num 不是序列起点，直接跳过if(!hash.count(num-1)){// 此时 num 是一个新序列的起点intcurrentNum=num;intcurrentStreak=1;// 顺藤摸瓜，不断在哈希表中寻找下一个连续的数字while(hash.count(currentNum+1)){currentNum+=1;currentStreak+=1;}// 更新全局最长序列长度res=max(res,currentStreak);}}returnres;}};