yicong@algo: ~/code/01-hash/0128-longest-consecutive-sequence.cpp

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;
}