给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n)的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
示例 3：
输入：nums = [1,0,1,2]
输出：3
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109
我第一开始想的是红黑树解法
红黑树
解题思路：利用红黑树的“自动排序”与“去重”特性
在 C++ 中，std::map 的底层是由红黑树实现的。当我们把一组无序的数字插入到 map 中时，它会自动帮我们完成两件事：
- 去重：相同的数字只保留一个（对应代码中判断
m.end()的部分）。 - 排序：所有的 key 会自动按照从小到大的顺序排好。
有了这两个天然优势，我们只需要遍历一遍排好序的 map，像数数一样看看当前的数字是不是刚好比前一个数字大 1。如果是，连续长度 count 就加 1；如果不是，说明断档了，count 重新从 1 开始算。并在每次循环的末尾，时刻更新历史最高记录 max。
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
// 1. 边界情况处理：拦截空数组
if (nums.empty()) {
return 0;
}
// 2. 利用 map 进行自动去重和排序
map<int, int> m;
for (auto& i : nums) {
if (m.find(i) == m.end()) {
m[i] = 1;
}
}
// 3. 初始化状态记录变量
int max = 1; // 记录历史最长连续序列的长度
int count = 1; // 记录当前正在计算的连续序列长度
int temp = m.begin()->first; // 记录前一个数字，用于和当前数字比对
// 4. 遍历有序的 map 寻找最长序列
for (auto& i : m) {
int start = i.first; // 获取当前数字
if (temp == start) {
// 循环的第一次，自己跟自己比，长度保持 1 不变
count = 1;
}
else if (temp + 1 == start) {
// 发现连续数字！当前长度+1，并将参照物推进一步
count++;
temp++;
}
else {
// 序列断开！重置参照物为当前新起点，当前长度打回原形
temp = start;
count = 1;
}
// 5. 每次推进后，立刻比对并更新最高记录
if (count > max) {
max = count;
}
}
return max;
}
};
复杂度分析
- 时间复杂度：O(nlogn)。遍历原数组并将 n 个元素插入到
map中，每次插入红黑树的时间复杂度是 O(logn)，总耗时 O(nlogn)。之后遍历map耗时 O(n)。综合起来最高量级为 O(nlogn)。 - 空间复杂度：O(n)。最坏情况下（数组中没有重复数字），
map需要存储 n 个键值对，占用 O(n) 的额外空间。
核心题解：最长连续序列（O(n) 哈希表解法）
1. 算法核心思想：只找“真正的起点”
要在 O(n) 的时间复杂度内解决此题，最大的难点在于如何避免重复数数。 如果对数组里的每一个数都向后循环查找，时间复杂度必定退化为 O(n2)。因此，我们的核心策略是：只对一段连续序列的“起点（老大）”进行向后查找，遇到“中间节点（小弟）”直接跳过。
- 如何判断一个数
x是不是起点？ 极其简单：只要哈希表里不存在x - 1，那x就是一个全新序列的起点！
2. 解题三步曲
- 装麻袋（去重与 O**(1) 查找）**：遍历一次原数组，把所有数字存入哈希表（
unordered_map或unordered_set）。这一步不仅去除了会导致超时的重复数字，还让我们后续查找某个数是否存在的耗时降到了极速的 O(1)。 - 找老大（精准拦截）：遍历哈希表中的每一个数字
num，去查num - 1存不存在。如果存在，说明它只是个中间节点，直接continue略过。 - 顺藤摸瓜（统计长度）：如果
num - 1不存在，确认它是起点。立刻开启while循环，不断查找num + 1、num + 2……直到序列断开。最后拿当前序列的长度去挑战历史最高记录max。
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
// 1. 边界防御：空数组直接返回 0
if (nums.empty()) {
return 0;
}
// 2. 装填哈希表：利用哈希表特性去重，并提供 O(1) 查找
unordered_map<int, int> map;
for (auto& num : nums) {
map.insert({num, 1});
}
int max_len = 1;
// 3. 遍历哈希表（注意：这里必须遍历哈希表以防重复数字拖慢速度）
for (auto& m : map) {
int num = m.first; // 取出真正的数字
// 【核心灵魂】如果前面有数字，说明它是小弟，直接跳过！
if (map.find(num - 1) != map.end()) {
continue;
}
// 走到这里的，绝对是全新的序列起点
int tmp = num;
int count = 1;
// 顺藤摸瓜，疯狂往后找连续的数字
while (map.find(tmp + 1) != map.end()) {
tmp++;
count++;
}
// 序列断开后，更新最长记录
if (count > max_len) {
max_len = count;
}
}
return max_len;
}
};
4. 复杂度深度剖析
- 时间复杂度：O(n) 虽然代码里是
for循环里面套了一个while循环，看起来像 O(n2)，但这是个障眼法。 因为有if (map.find(num - 1) != map.end()) { continue; }的神级拦截，哈希表里的绝大多数数字在for循环里直接就被continue踢走了。只有真正的起点才会触发while循环。综合算下来，数组里的每一个数字，真正在while循环里被处理的次数绝对不超过 1 次。因此总时间复杂度依然是线性的 O(n)。 - 空间复杂度：O(n) 最坏情况下（所有数字都不重复），哈希表需要存储 n 个数字，额外占用 O(n) 的内存空间。这属于典型的“用空间换时间”。