题意概括

给定一个未排序的整数数组，找出其中最长的连续数字序列的长度。这里的“连续”指的是数值上的连续（如 1, 2, 3, 4），而这些数字在原数组中的位置不必相邻。题目要求算法的时间复杂度为 $O(N)$。

数据范围:

• $0 \le N \le 10^5$
• 数组中的元素为 int 范围内的整数。

基础知识

本题的核心要求是 $O(N)$ 的时间复杂度，这直接排除了基于排序的 $O(N \log N)$ 解法。为了实现线性时间复杂度，我们需要一种能够快速（平均 $O(1)$）查询一个数是否存在的数据结构，哈希表 (在 C++ 中常用 std::unordered_set) 是理想的选择。

算法思路 (哈希表优化):

1. 存入哈希表: 首先，遍历一遍输入数组，将所有数字存入一个哈希集合 (unordered_set) 中。这一步的目的是为了后续能够快速判断某个数字是否存在于数组中。此操作的平均时间复杂度为 $O(N)$。

2. 寻找序列起点: 再次遍历数组中的每个数字 x。对于每个 x，我们进行一个关键的优化判断：检查 x-1 是否存在于哈希表中。

   • 如果 x-1 不存在，那么 x 就可能是一个连续序列的起点。我们从 x 开始，向后不断地检查 x+1, x+2, x+3... 是否存在于哈希表中，并用一个计数器 cur 记录当前连续序列的长度。
   • 如果 x-1 存在，那么 x 肯定不是一个连续序列的起点（因为它属于以某个更小的数字开头的序列的一部分）。因此，我们可以直接跳过 x，不进行任何计数操作。

3. 更新结果: 每当从一个序列起点开始的计数结束后，就用得到的长度 cur 去更新全局的最大长度 ans。

这个算法的巧妙之处在于 x-1 的判断。它确保了每个连续序列只会被其开头的那个数字触发一次计数循环，从而避免了重复计算。尽管代码看起来有两层循环，但内层循环在整个算法的执行过程中，其总的执行次数不会超过 $N$ 次。因此，总的时间复杂度为 $O(N)$，空间复杂度为 $O(N)$（用于哈希表）。

C++ 解决方案

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void slv() {
    int n;
    cin >> n;

    if (n == 0) {
        cout << 0 << endl;
        return;
    }

    unordered_set<int> s;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
        s.insert(v[i]);
    }

    int ans = 0;

    // 遍历哈希表中的每一个数
    for (int x : s) {
        // 关键优化：只对没有前驱的数（序列的起点）进行处理
        if (s.find(x - 1) == s.end()) {
            int cur = 1;
            int y = x + 1;

            // 从起点开始，向后查找连续的数
            while (s.count(y)) {
                cur++;
                y++;
            }

            // 更新最大长度
            ans = max(ans, cur);
        }
    }

    cout << ans << endl;
}

int main() {
    // 关闭同步流，加速IO
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    slv();

    return 0;
}

/*
样例输入 1:
6
100 4 200 1 3 2

样例输出 1:
4

样例输入 2:
10
0 3 7 2 5 8 4 6 0 1

样例输出 2:
9
*/