yicong@algo:~/code/01-hash$ cat 0128-longest-consecutive-sequence.cpp
128. 最长连续序列
// 思路
所有数放进哈希集合;只从「没有前驱 x-1」的数开始向后数
// 时间复杂度
O(n)
// 空间复杂度
O(n),哈希集合存下去重后的所有数
// 易错点
不要对每个数都向后数,否则退化成 O(n^2)
// 面试口述要点
为什么只从序列起点开始枚举,总复杂度仍然是 O(n)?
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> s;
for (int x : nums) s.insert(x);
int ans = 0;
for (int x : s){
if (s.count(x-1)) continue;
int m = 1;
int y = x;
while(s.count(y+1)){
y++;
m++;
}
if (m > ans) ans = m;
}
return ans;
}
};
// 本地测试:输入 n,然后 n 个整数;输出最长连续序列长度
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
vector<int> nums(n);
for (int& x : nums) cin >> x;
cout << Solution().longestConsecutive(nums) << '\n';
return 0;
}