题解 | 数组中的最长连续子序列

#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

int main() 
{
    int n;
    cin >> n;

    vector<int> nums(n);
    for(int i = 0; i < n; i++)
        cin >> nums[i];
    
    unordered_set<int> hash;
    for(auto x : nums) hash.insert(x);

    int max_len = 0;
    for(auto x : nums)
    {
        int len = 1;
        if(hash.count(x - 1)) continue;
        while(hash.count(x + 1)) 
        {
            x += 1;
            len++;
        }
        max_len = max(max_len, len);
    }

    cout << max_len << endl;
    return 0;
}

1. 预处理：将所有元素存入哈希集合 hash，以便快速判断某个数是否存在（时间复杂度 O (1)）。
2. 遍历与计数：对于每个元素 x，检查它是否是一个连续序列的起点（即 x-1 不在集合中）。如果是起点，则从 x 开始不断检查 x+1, x+2, ... 是否存在，并记录当前序列的长度。更新全局最长长度 max_len。