📍 题目背景
今天咱们来手撕 LeetCode 上一道极具迷惑性的经典大题：[128. 最长连续序列]。 这道题不仅考察了常规的数组操作，更是一块检验程序员底层功底的绝佳“试金石”！题目最后还有一句灵魂要求：“你必须设计并实现时间复杂度为O(n)的算法解决此问题。”
【题目描述】给定一个未排序的整数数组nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
【示例】
输入:nums =
[100, 4, 200, 1, 3, 2]输出:4解释:最长数字连续序列是[1, 2, 3, 4]。它的长度为 4。
💡 方法一：直观的排序法 (时间复杂度 O(N log N))
人类最直观的思维：既然要找连续的数字，那把它们从小到大排个序，挨个往后数不就行了？
【核心避坑点】
空数组兜底：遇到
[]直接返回 0。重复数字跳过：比如
[1, 2, 2, 3]，遇到相等的数字要直接无视，不能打断连续状态。断网重连机制：一旦发现数字不连续（比如遇到跳跃的数字），必须立刻结算当前最高纪录，并将连击数清零（变回 1）重新开始计算。
💻 排序法 C++ 代码
#include <iostream> #include <vector> #include <algorithm> using namespace std; class Solution { public: int longestConsecutive(vector<int>& nums) { if(nums.empty()) return 0; sort(nums.begin(), nums.end()); int curr = 1; int max_curr = 1; for(int i = 1; i < nums.size(); i++) { if(nums[i] != nums[i-1]) { // 忽略重复元素 if(nums[i] - 1 == nums[i-1]) { curr += 1; // 连续，连击数 +1 } else { max_curr = max(max_curr, curr); // 断开连续，结算最高分 curr = 1; // 重新开始连击 } } // 每次循环末尾稳妥更新纪录，防止最长序列在末尾 max_curr = max(curr, max_curr); } return max_curr; } };🚀 方法二：哈希表的“降维打击” (时间复杂度 O(N))
为了满足题目O(N)的要求，我们需要放弃排序，直接祭出终极大杀器：哈希集合（unordered_set）。
【核心逻辑：只找排头兵】
将所有数字扔进哈希表中去重，并获得
O(1)的查询速度。扫描数字时，判断
num - 1是否存在。如果存在，说明它只是队伍里的小兵，直接跳过！只有当
num - 1不存在时，说明它是这支连续队伍的“开头排头兵”。此时才开启while循环，顺藤摸瓜寻找num + 1，直到队伍结束。
💻 哈希表法 C++ 代码
#include <iostream> #include <vector> #include <unordered_set> #include <algorithm> using namespace std; class Solution { public: int longestConsecutive(vector<int>& nums) { if(nums.empty()) return 0; // 1. 数据全部丢进超级雷达（哈希表） unordered_set<int> us(nums.begin(), nums.end()); int curr_max = 0; for(auto num : us) { // 2. 只有发现“排头兵”才允许进入循环顺藤摸瓜 if(!us.count(num - 1)) { int curr_num = num; int curr = 1; // 3. 顺着排头兵往下找 while(us.count(curr_num + 1)) { curr_num += 1; curr += 1; } // 4. 结算当前队伍的最高纪录 curr_max = max(curr, curr_max); } } return curr_max; } };🤯 深度硬核解析：为什么 O(N) 实际运行比 O(N log N) 慢？
在 LeetCode 的实际提交中，你会发现一个违背直觉的现象：
排序法($O(N \log N)$) 耗时约14ms。
哈希表法($O(N)$) 耗时高达94ms。
难道理论错了吗？不，这是底层物理法则的限制！面试大厂如果能答出以下两点，直接拿满分：
哈希表建表的“隐藏代价”极大： C++ 中的
sort是基于内省排序，只需在连续内存中原地位移即可，极其轻量。而构建unordered_set需要计算哈希值、分配内存、处理冲突。遇到哈希碰撞或需要扩容（Rehash）时，底层会消耗大量的额外时间，这个“常数代价”极其惊人。CPU 缓存未命中 (Cache Miss)： 数组在内存中是连续存储的，CPU 在读取当前数字时，会顺手将后面的数字全部拉入高速缓存，读取速度飞快；而哈希表在内存中是随机分布的，CPU 经常在缓存中找不到下一个节点，只能被迫去慢速内存中寻址，这被称作“缓存未命中”，会严重拖慢运行效率。
💡 总结：理论上的最优解不一定是工程上的最快解。在数据量 $N$ 只有十万级别时，哈希表的常数耗时抵消了 $O(N)$ 的优势。只有当数据量上亿，$\log N$ 变得极其巨大时，哈希表的碾压姿态才会显现。
