当前位置：首页 > news >正文

力扣刷题#11：LeetCode128最长连续序列_刷题笔记

news 2026/6/8 21:57:16

力扣刷题#11：LeetCode128最长连续序列_刷题笔记

题目描述

给定一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例：

输入：nums = [100, 4, 200, 1, 3, 2]
输出：4
解释：最长连续序列是 [1, 2, 3, 4]，长度为 4。

Step 1：先想一个直觉解法（排序 + 双指针）

最朴素的想法：

排序 → 相邻元素比较，遇到不连续的就重置计数

sort(nums.begin(), nums.end());
int ans = 1, cur = 1;
for (int i = 1; i < n; i++) {if (nums[i] == nums[i - 1]) continue;      // 跳过重复if (nums[i] == nums[i - 1] + 1) cur++;      // 连续else { ans = max(ans, cur); cur = 1; }      // 断了
}

复杂度	值	说明
时间复杂度	O(n log n)	排序是瓶颈
空间复杂度	O(1)	原地排序

题目要求 O(n)，所以排序不行。那怎么去掉 log n 的排序开销？

Step 2：用哈希集合存储所有元素

把数组元素放进 unordered_set，就可以 O(1) 查值了。

unordered_set<int> s(nums.begin(), nums.end());

简单粗暴的想法（会超时）

对每个数，往后查连续数字：

for (int num : nums) {int t = num, len = 1;while (s.count(++t)) len++;ans = max(ans, len);
}

问题：大量重复遍历！

nums = [1, 2, 3, 4]
从 1 出发：查到 2, 3, 4   ✅
从 2 出发：查到 3, 4       💥 重复
从 3 出发：查到 4          💥 重复
从 4 出发：查不到          ✅

最坏情况 O(n²) —— 这就是上一版超时的原因。

Step 3：关键优化——只从序列起点开始查

什么数是序列的起点？

一个数字是序列的起点，当且仅当 num - 1 不在 set 中。

[1, 2, 3, 4] 中：1: 0 不在 set → ✅ 起点2: 1 在 set   → ❌ 不是起点3: 2 在 set   → ❌ 不是起点4: 3 在 set   → ❌ 不是起点

只有从起点出发，才能查到完整序列；从中间出发查到的都是 「已经被走过的路」。

加上起点判断后，每个元素最多被遍历一次

修正后的逻辑：

for (const int& num : s) {                    // 遍历 set（去重）if (s.count(num - 1) == 0) {               // 是起点int t = num, cns = 1;while (s.count(++t)) cns++;            // 往后延展ans = max(ans, cns);                   // 出循环再 max}
}

为什么复杂度是 O(n)？

每个数只有作为起点时才进入 while 循环
while 循环里遍历的每个数不会被第二个起点再遍历到
所有 while 累计总步数 ≤ 数组长度

踩坑记录

❌ Bug 1：变量名写混

unordered_set<int> s;
s.insert(nums[i]);   // ✅ 正确
// set.insert(nums[i]);  // ❌ s 写成了 set

❌ Bug 2：`cns` 忘记声明类型

cns = 1;   // ❌ 编译错误
int cns = 1;  // ✅

❌ Bug 3：while 结束后没更新 m

while (...) { m = max(m, ++cns); }   // 🔴 每次都 max，浪费

while (...) { cns++; }               // 只自增
m = max(m, cns);                     // 循环结束再 max

❌ Bug 4：重复元素导致超时

遍历 nums 而不是 set 会导致相同值的元素反复触发相同的 while 循环，最坏情况 O(n²)。

修复：遍历 set 而非 nums。

最终 AC 代码

class Solution {
public:int longestConsecutive(vector<int>& nums) {if (nums.empty()) return 0;unordered_set<int> s(nums.begin(), nums.end());int ans = 0;for (const int& num : s) {if (s.count(num - 1) == 0) {          // 是序列起点int t = num, cns = 1;while (s.count(++t)) cns++;       // 往后延展ans = max(ans, cns);              // 更新最大值}}return ans;}
};