128. 最长连续序列
一句话套路set + 只在连续段起点向右扩
题目描述
给定一个未排序的整数数组 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
思路
时间
O(n)空间
O(n)思路
全部丢进 unordered_set。只对「一段连续区间的起点」展开向右延伸,起点判定 = set 里不存在 num-1。这样每个数最多被访问两次 -> O(n)。
关键
不做起点判定的话,[1,2,3,4] 会从 1 和 2 都往右扫,退化成 O(n^2)。
题目明确要求 O(n),所以「排序后扫描」的 O(n log n) 只能算备用解。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0128 {
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> pool(nums.begin(), nums.end()); // 顺便去重
int best = 0;
for (int x : pool) {
if (pool.count(x - 1)) continue; // 不是起点,跳过
int cur = x, len = 0;
while (pool.count(cur)) {
++len;
++cur; // 向右延伸
}
best = max(best, len);
}
return best;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0128::Solution s;
vector<int> a{100, 4, 200, 1, 3, 2};
CHECK_EQ(s.longestConsecutive(a), 4); // 1,2,3,4
vector<int> b{0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
CHECK_EQ(s.longestConsecutive(b), 9); // 0..8,重复的 0 不影响
vector<int> c{};
CHECK_EQ(s.longestConsecutive(c), 0);
vector<int> d{1};
CHECK_EQ(s.longestConsecutive(d), 1);
vector<int> e{-1, 0, 1}; // 含负数
CHECK_EQ(s.longestConsecutive(e), 3);