- 正确答案：使用哈希表（unordered_map）预存所有数字，然后对每个数字尝试向左右扩展连续序列，但仅当该数字是某个连续序列的起点时才进行扩展（即num-1不在哈希表中），从而保证每个数字最多被访问两次（一次在遍历中判断是否为起点，一次在扩展中被访问），整体时间复杂度为O(n)，空间复杂度O(n)。 - 解答思路： 1. 首先将所有数字插入unordered_map（或unordered_set），实现O(1)平均查找； 2. 遍历原数组，对每个数num，检查num-1是否存在——若存在，说明num不是某连续序列的起点，跳过； 3. 若num-1不存在，则num是起点，开始向右连续递增查找（num+1, num+2,…），同时向左查找（num-1已知不存在，故只需向右扩展即可，但严格来说也可双向扩展，不过单向已足够）； 4. 统计当前连续长度，更新全局最大值； 5. 注意：由于每个数字至多作为一次“起点”被扩展，且每次扩展中每个数字至多被访问一次（因非起点数字永远不触发扩展），因此总操作次数≤2n，满足O(n)。关键优化点在于“只从连续序列最小值开始扩展”，避免重复计算。 - 深度知识讲解：【底层数据结构原理】 unordered_map 是 C++ STL 中基于哈希表（Hash Table）实现的关联容器，其底层通常采用“开散列（open hashing）”即拉链法（separate chaining），以 vector>> 或 vector> 形式组织。每个桶（bucket）是一个链表（或前向链表），用于解决哈希冲突。C++11 标准要求其平均查找/插入/删除时间为 O(1)，最坏情况为 O(n)（所有元素哈希到同一桶，退化为链表遍历），但实际实现（如 libstdc++ 和 libc++）通过动态扩容（rehash）、质数桶数量、良好哈希函数等策略极大降低碰撞概率。【哈希函数与桶管理】对于整型 key，标准库通常使用 identity hash（即直接取整数值）或经位运算扰动后的值（如 murmur-like 混淆），再对当前桶数取模得到 bucket index。unordered_map 维护 load factor（α = 元素数 / 桶数），当 α 超过 max_load_factor（默认 1.0）时自动 rehash：分配新桶数组（通常翻倍或按质数序列增长），重新计算每个元素的 hash 并迁移。rehash 是 O(n) 操作，但均摊后仍为 O(1)。【内存布局与性能特性】 unordered_map 的节点通常动态分配（每个 {key,value} 单独 new），导致缓存不友好（对比 vector 连续内存）；而 unordered_set 仅存 key，更省内存。其迭代器不保证顺序（无序），且不支持下标随机访问（无 operator[] 的 const 版本需谨慎，非 const [] 会插入默认构造值）。erase 操作后，除被删元素外，其余迭代器不失效（这是与 map 的重要区别）。【为什么不能用 map？】 map 基于红黑树，查找/插入为 O(log n)，若用 map 实现本题，外层遍历 O(n)，内层扩展最坏 O(n)（如全有序数组），总时间 O(n² log n)，不满足要求。而 unordered_map 提供均摊 O(1) 查找，是达成 O(n) 的必要条件。【进阶追问点解析】 - Q：unordered_map 的 key 类型必须满足什么条件？ A：必须可哈希（即提供 std::hash 特化，或自定义哈希函数对象）、可比较相等（支持 == 运算符）。内置类型（int, string 等）均已特化；自定义类需显式定义 hash 和 ==，或传入仿函数。 - Q：如何自定义 unordered_map 的哈希函数和相等比较？ A：例如对 pair 作 key： struct pair_hash { size_t operator()(const pair& p) const { return hash()((static_cast(p.first) << 32) ^ p.second); } }; unordered_map, int, pair_hash> mp; - Q：unordered_map 是否线程安全？ A：读操作（const 成员函数如 find、at）在无写操作并发时是线程安全的；但 insert/erase/modifying 非 const 操作需外部同步（如 mutex）。STL 容器均不提供内部线程安全。 - Q：如果输入含大量重复数字，会影响算法吗？ A：不影响。我们用 unordered_set 更合适（只需判存），但即使用 unordered_map，重复插入会被忽略（或覆盖），且后续遍历时去重逻辑天然成立（重复数字不会多次触发起点判定，因 set 查找结果相同）。 - 代码示例（C++，完整可运行逻辑）： #include #include #include using namespace std; int longestConsecutive(vector& nums) { if (nums.empty()) return 0; unordered_set numSet(nums.begin(), nums.end()); // O(n) 构建 int maxLength = 0; for (int num : nums) { // 只有当 num 是连续序列起点时才扩展 if (numSet.find(num - 1) == numSet.end()) { int currentNum = num; int currentLength = 1; // 向右扩展：num+1, num+2, ... while (numSet.find(currentNum + 1) != numSet.end()) { currentNum++; currentLength++; } maxLength = max(maxLength, currentLength); } } return maxLength; } // 注：上述代码中，while 循环内每次 find 是 O(1) 均摊，每个数字最多进入 while 一次（仅当为起点），故总循环体执行次数 ≤ n； // 外层 for 是 n 次，每次 find(num-1) 也是 O(1)，故总时间复杂度严格 O(n)。 - 扩展知识：该题本质考察“哈希加速离线查询 + 避免重复计算”的思想，类似技巧还见于： • “两数之和”（用哈希表存 complement）； • “岛屿数量”中用 visited set 防止重复 DFS； • 并查集（Union-Find）的路径压缩与按秩合并，也追求均摊 O(α(n)) 接近 O(1)，但实现更复杂； • 在大数据场景，该算法可推广至分布式：分片存储数字 → 各节点本地找局部起点 → 合并跨分片边界序列（需传递 min/max 边界信息）。最后提醒面试者：回答时务必强调“为何是 O(n)”——不是因为用了哈希表就自动 O(n)，而是控制了每个元素最多被常数次访问，这是算法设计的关键洞察。

测开算法题手撕

全站热榜

创作者周榜