LeetCode Hot100【哈希-128.最长连续序列】

标题：128. 最长连续序列

1. class Solution {
2. public:
3.     int longestConsecutive(vector<int>& nums) {
4.         unordered_set<int> num_set;  // 使用哈希集合存储数组元素
5.         for (const int& num : nums) {
6.             num_set.insert(num);  // 插入数组中的每个数
7.         }
9.         int longestStreak = 0;  // 记录最长连续序列的长度
11.         for (const int& num : num_set) {
12.             // 如果 num - 1 不在集合中，则 num 是序列的起点
13.             if (!num_set.count(num - 1))
14. {
15.                 int currentNum = num;
16.                 int currentStreak = 1;
18.                 // 检查是否存在 num + 1, num + 2, ..., 形成连续序列
19.                 while (num_set.count(currentNum + 1)) {
20.                     currentNum += 1;
21.                     currentStreak += 1;
22.                 }
24.                 // 记录最大长度
25.                 longestStreak = max(longestStreak, currentStreak);
27.             }
28.         }
29.         return longestStreak;
30.     }
31. };

复制代码

实行流程

1. nums = {100, 4, 200, 1, 3, 2}
2. ;

复制代码

实行步调如下：

步调 1：构建 unordered_set

哈希集合 num_set 存储：

1. {100, 4, 200, 1, 3, 2}

复制代码

步调 2：遍历 num_set 并计算最长连续序列

遍历元素

• num = 100
  - num - 1 = 99 不在 num_set，但 num + 1 = 101 也不在。
  - currentStreak = 1，最长序列长度更新为 1。
  
• num = 4
  - num - 1 = 3 在 num_set，跳过（4 不是起点）。
  
• num = 200
  - num - 1 = 199 不在 num_set，但 num + 1 = 201 也不在。
  - currentStreak = 1，最长序列长度仍为 1。
  
• num = 1
  - num - 1 = 0 不在 num_set，1 是序列起点。
  - 计算连续序列 1 → 2 → 3 → 4，currentStreak = 4。
  - longestStreak = max(1, 4) = 4。
  最终返回 longestStreak = 4。
  

时间 & 空间复杂度

操作时间复杂度空间复杂度插入 unordered_setO(n)O(n)遍历 unordered_setO(n)O(1)查询 unordered_set.count()O(1)O(1) 最终

• 时间复杂度：O(n)（每个元素最多访问两次）。
  
• 空间复杂度：O(n)（存储 unordered_set）。
  

关键点解析

• 哈希表加速查找：传统暴力解法是 双重循环（O(n²)），利用 unordered_map 将查找优化到 O(1) 。
  
• 边查找边插入：包管不会取到相同元素的索引，比方 [3, 3] 这样的情况。
  

优化 & 变种

假如 nums 颠末 排序，可以利用 O(n log n) 的解法：

1. int longestConsecutive(vector<int>& nums) {
2.     if (nums.empty()) return 0;
3.     sort(nums.begin(), nums.end());
4.     int longest = 1, current = 1;
6.     for (int i = 1; i < nums.size(); i++) {
7.         if (nums[i] == nums[i - 1]) continue;  // 跳过重复项
8.         if (nums[i] == nums[i - 1] + 1) {
9.             current += 1;
10.         } else {
11.             longest = max(longest, current);
12.             current = 1;
13.         }
14.     }
15.     return max(longest, current);
16. }

复制代码

但 哈希表解法更优，因为 无需排序，时间复杂度更低（O(n)）。

---

基础知识

1. unordered_set<int>

1. unordered_set<int> num_set;

复制代码

• C++ STL 提供的哈希集合，底层基于哈希表，查询平均复杂度为 O(1)。
  
• 去重特性：集合中不能有重复元素。
  

基本操作

1. unordered_set<int> s;
2. s.insert(10);
3. s.count(10); // 返回 1，表示存在
4. s.count(5);  // 返回 0，表示不存在

复制代码

2. for (const int& num : num_set)

1. for (const int& num : num_set) { ... }

复制代码

• 基于范围的 for 遍历，避免利用索引。
  
• 利用 const int& num 避免拷贝，进步性能。
  

3. num_set.count(num - 1)

1. if (!num_set.count(num - 1))

复制代码

• count(x) 查抄集合中是否有 x，返回 1 或 0。
  
• 假如 num - 1 不存在，则 num 是一个新的连续序列的起点。
  

4. while (num_set.count(currentNum + 1))

1. while (num_set.count(currentNum + 1)) {
2.     currentNum += 1;
3.     currentStreak += 1;
4. }

复制代码

• 不断查抄 num + 1 是否存在，直到连续序列断开。
  

示例

1. unordered_set<int> s = {1, 2, 3, 4};
2. int num = 1, streak = 1;
4. while (s.count(num + 1)) {
5.     num += 1;   // num 变成 2, 3, 4
6.     streak += 1; // streak 变成 2, 3, 4
7. }

复制代码

最终 streak = 4。
5. max(longestStreak, currentStreak)

1. longestStreak = max(longestStreak, currentStreak);

复制代码

• 取最大值，确保 longestStreak 存储最长的连续序列。
  

总结

C++语法作用unordered_set哈希集合（去重 & 快速查询）for (const int& num : num_set)遍历哈希表count(x)查抄集合是否包罗 xwhile (num_set.count(currentNum + 1))查找连续元素max(a, b)取最大值
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。