【算法日记15】LeetCode 128. 最长连续序列：排序法 vs 哈希表的底层真相
·
📍 题目背景
今天咱们来手撕 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 经常在缓存中找不到下一个节点，只能被迫去慢速内存中寻址，这被称作“缓存未命中”，会严重拖慢运行效率。
最后附上动态演示
<!DOCTYPE html>
<html lang="zh-CN">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>哈希表魔法：最长连续序列</title>
<script src="https://cdn.tailwindcss.com"></script>
<style>
.node-transition { transition: all 0.4s cubic-bezier(0.4, 0, 0.2, 1); }
/* 默认状态 */
.node-default { border-color: #e5e7eb; background-color: #ffffff; color: #374151; }
/* 正在检查当前数字 */
.node-current { box-shadow: 0 0 15px rgba(59, 130, 246, 0.6); border-color: #3b82f6; background-color: #eff6ff; transform: scale(1.1); z-index: 10; }
/* 确认为排头兵 */
.node-leader { box-shadow: 0 0 15px rgba(245, 158, 11, 0.6); border-color: #f59e0b; background-color: #fef3c7; transform: scale(1.1); z-index: 10; }
/* 是小弟，直接跳过 */
.node-skip { opacity: 0.4; border-color: #d1d5db; background-color: #f3f4f6; }
/* 顺藤摸瓜找到的连续数字 */
.node-chain { box-shadow: 0 0 15px rgba(16, 185, 129, 0.6); border-color: #10b981; background-color: #ecfdf5; transform: scale(1.1); z-index: 5; color: #047857; }
/* 正在哈希表中探寻下一个目标 */
.node-searching { border-color: #8b5cf6; background-color: #f5f3ff; border-style: dashed; }
</style>
</head>
<body class="bg-gray-50 min-h-screen flex flex-col items-center justify-center p-4 font-sans text-gray-800">
<div class="max-w-4xl w-full bg-white rounded-2xl shadow-xl overflow-hidden">
<!-- 头部标题 -->
<div class="bg-gradient-to-r from-blue-600 to-indigo-600 text-white p-6 text-center">
<h1 class="text-3xl font-bold mb-2">⚡ 哈希表降维打击：最长连续序列</h1>
<p class="text-indigo-100">LeetCode 128. O(N) 复杂度精髓：只找排头兵，跳过小跟班</p>
</div>
<!-- 动画主界面 -->
<div class="p-8">
<!-- 讲解信息框 -->
<div class="bg-blue-50 border-l-4 border-blue-500 p-5 rounded-r-xl mb-8 min-h-[100px] flex items-center shadow-sm">
<p id="message-box" class="text-lg font-medium text-blue-900 leading-relaxed">
准备开始！点击“下一步”或“自动播放”观察哈希表是如何施展魔法的。
</p>
</div>
<div class="flex flex-col md:flex-row gap-8 mb-10">
<!-- 哈希表展示区 -->
<div class="flex-1 bg-gray-50 rounded-xl p-6 border-2 border-gray-100 shadow-inner">
<h2 class="text-gray-500 font-bold mb-4 text-center">超级雷达 (unordered_set)</h2>
<div class="flex flex-wrap justify-center gap-4" id="hashset-container">
<!-- 这里的方块由 JS 动态生成 -->
</div>
</div>
<!-- 战况统计区 -->
<div class="w-full md:w-48 flex flex-col gap-4">
<div class="bg-white p-4 rounded-xl shadow border border-gray-100 text-center">
<div class="text-sm text-gray-500 font-semibold mb-1">当前序列长度</div>
<div id="curr-len" class="text-3xl font-bold text-blue-600">0</div>
</div>
<div class="bg-white p-4 rounded-xl shadow border border-yellow-200 text-center relative overflow-hidden">
<div class="absolute top-0 left-0 w-full h-1 bg-yellow-400"></div>
<div class="text-sm text-yellow-600 font-semibold mb-1">历史最高纪录</div>
<div id="max-len" class="text-4xl font-black text-yellow-500">0</div>
</div>
</div>
</div>
<!-- 控制按钮区 -->
<div class="flex justify-center gap-4">
<button id="btn-reset" class="px-6 py-2.5 bg-gray-200 hover:bg-gray-300 text-gray-700 font-semibold rounded-full transition-colors shadow">
🔄 重置
</button>
<button id="btn-step" class="px-6 py-2.5 bg-indigo-500 hover:bg-indigo-600 text-white font-semibold rounded-full shadow-md transition-colors transform hover:scale-105">
👣 下一步
</button>
<button id="btn-play" class="px-6 py-2.5 bg-green-500 hover:bg-green-600 text-white font-semibold rounded-full shadow-md transition-colors transform hover:scale-105">
▶️ 自动播放
</button>
</div>
<!-- 图例 -->
<div class="mt-8 flex flex-wrap justify-center gap-6 text-sm font-bold text-gray-600">
<div class="flex items-center gap-2"><span class="w-4 h-4 rounded-full border-2 border-blue-500 bg-blue-100"></span> 正在扫描</div>
<div class="flex items-center gap-2"><span class="w-4 h-4 rounded-full border-2 border-yellow-500 bg-yellow-100"></span> 排头兵 (发起连击)</div>
<div class="flex items-center gap-2"><span class="w-4 h-4 rounded-full border-2 border-green-500 bg-green-100"></span> 连续队伍成员</div>
<div class="flex items-center gap-2"><span class="w-4 h-4 rounded-full border-2 border-gray-300 bg-gray-200 opacity-50"></span> 小弟 (直接跳过)</div>
</div>
</div>
</div>
<script>
const nums = [100, 4, 200, 1, 3, 2];
let currentFrameIndex = 0, isPlaying = false, playInterval, frames = [];
function generateFrames() {
frames = [];
let maxLen = 0;
const set = new Set(nums);
frames.push({
activeNums: [], currLen: 0, maxLen: 0,
msg: "【阶段 1】将数组 `[100, 4, 200, 1, 3, 2]` 全部扔进哈希表。<br>哈希表自带去重功能，并且拥有 <b>O(1) 的超快查询速度</b>！"
});
for (let i = 0; i < nums.length; i++) {
let num = nums[i];
let prev = num - 1;
frames.push({
current: num, currLen: 0, maxLen: maxLen,
msg: `扫描数字 <b>${num}</b>。开始灵魂拷问：它是排头兵吗？<br>去雷达里找找有没有它的前一个数字 <b>${prev}</b>。`
});
if (set.has(prev)) {
frames.push({
current: num, skip: true, currLen: 0, maxLen: maxLen,
msg: `雷达发现 <b>${prev}</b> 存在！说明 <b>${num}</b> 只是个小弟，直接跳过，绝不浪费时间！💨`
});
} else {
frames.push({
current: num, leader: true, currLen: 1, maxLen: maxLen, chain: [num],
msg: `雷达未发现 <b>${prev}</b>。确认 <b>${num}</b> 是排头兵！👑<br>开启 while 循环，准备顺藤摸瓜找下一个数字。`
});
let currNum = num;
let currLen = 1;
let chain = [num];
while (set.has(currNum + 1)) {
frames.push({
current: num, leader: true, currLen: currLen, maxLen: maxLen, chain: [...chain], searching: currNum + 1,
msg: `雷达呼叫 <b>${currNum + 1}</b>... 收到回复！存在！`
});
currNum += 1;
currLen += 1;
chain.push(currNum);
frames.push({
current: num, leader: true, currLen: currLen, maxLen: maxLen, chain: [...chain],
msg: `连击成功！将 <b>${currNum}</b> 编入连续队伍。目前长度：${currLen}`
});
}
frames.push({
current: num, leader: true, currLen: currLen, maxLen: maxLen, chain: [...chain], searching: currNum + 1,
msg: `雷达呼叫 <b>${currNum + 1}</b>... 无人回应。队伍断开。`
});
if (currLen > maxLen) {
maxLen = currLen;
frames.push({
current: num, leader: true, currLen: currLen, maxLen: maxLen, chain: [...chain],
msg: `🎉 结算连击数！新长度 <b>${currLen}</b> 打破了历史最高纪录！更新最大值。`
});
} else {
frames.push({
current: num, leader: true, currLen: currLen, maxLen: maxLen, chain: [...chain],
msg: `结算连击数！当前长度 <b>${currLen}</b> 没有打破最高纪录。`
});
}
}
}
frames.push({
maxLen: maxLen, currLen: 0,
msg: `🏁 扫描结束！<br>发现了吗？数组里虽然有 6 个数字，但 <b>while 循环总共只执行了 6 次</b>！这就是 O(N) 的魔法！`
});
}
function render() {
const frame = frames[currentFrameIndex];
// 更新文字
document.getElementById('message-box').innerHTML = frame.msg;
document.getElementById('curr-len').innerText = frame.currLen !== undefined ? frame.currLen : 0;
document.getElementById('max-len').innerText = frame.maxLen !== undefined ? frame.maxLen : 0;
// 渲染哈希表节点
const container = document.getElementById('hashset-container');
container.innerHTML = '';
nums.forEach(val => {
const box = document.createElement('div');
let classes = 'w-14 h-14 md:w-16 md:h-16 flex items-center justify-center text-xl font-bold border-4 rounded-full node-transition ';
// 状态机判断
if (frame.searching === val) {
classes += 'node-searching';
} else if (frame.chain && frame.chain.includes(val)) {
classes += 'node-chain';
if(val === frame.current && frame.leader) {
classes += ' node-leader'; // 排头兵特殊高亮
}
} else if (frame.current === val) {
if (frame.skip) classes += 'node-skip';
else if (frame.leader) classes += 'node-leader';
else classes += 'node-current';
} else {
classes += 'node-default';
}
box.className = classes;
box.innerText = val;
container.appendChild(box);
});
// 按钮状态
const isEnd = currentFrameIndex >= frames.length - 1;
document.getElementById('btn-step').disabled = isEnd;
document.getElementById('btn-step').className = isEnd
? "px-6 py-2.5 bg-gray-300 text-gray-500 font-semibold rounded-full cursor-not-allowed shadow"
: "px-6 py-2.5 bg-indigo-500 hover:bg-indigo-600 text-white font-semibold rounded-full shadow-md transition-colors transform hover:scale-105";
}
// 事件监听
document.getElementById('btn-step').addEventListener('click', () => {
if (currentFrameIndex < frames.length - 1) { currentFrameIndex++; render(); }
});
document.getElementById('btn-reset').addEventListener('click', () => {
currentFrameIndex = 0; if(isPlaying) togglePlay(); render();
});
document.getElementById('btn-play').addEventListener('click', togglePlay);
function togglePlay() {
const playBtn = document.getElementById('btn-play');
if (isPlaying) {
clearInterval(playInterval);
playBtn.innerHTML = '▶️ 自动播放';
playBtn.classList.replace('bg-yellow-500', 'bg-green-500');
playBtn.classList.replace('hover:bg-yellow-600', 'hover:bg-green-600');
isPlaying = false;
} else {
if (currentFrameIndex >= frames.length - 1) currentFrameIndex = 0;
playBtn.innerHTML = '⏸️ 暂停播放';
playBtn.classList.replace('bg-green-500', 'bg-yellow-500');
playBtn.classList.replace('hover:bg-green-600', 'hover:bg-yellow-600');
isPlaying = true;
playInterval = setInterval(() => {
if (currentFrameIndex < frames.length - 1) { currentFrameIndex++; render(); }
else { togglePlay(); }
}, 1500);
}
}
// 初始化启动
generateFrames();
render();
</script>
</body>
</html>
💡 总结： 理论上的最优解不一定是工程上的最快解。在数据量 $N$ 只有十万级别时，哈希表的常数耗时抵消了 $O(N)$ 的优势。只有当数据量上亿，$\log N$ 变得极其巨大时，哈希表的碾压姿态才会显现。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
5
0- 0
已为社区贡献3条内容
所有评论(0)