你好，同学。这道题是考查哈希表优化搜索的经典案例。在 NOI 竞赛中，如果题目要求 $O(n)$ 复杂度处理数值关系，通常意味着我们必须放弃排序，转而利用哈希表的 $O(1)$ 查找特性。

以下是基于 C++14 标准 的题解标准代码。

一、 最长连续序列 标准题解 (C++14)

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

using namespace std;

/**
 * 核心逻辑：哈希集合起点探测法
 * 1. 利用 unordered_set 将所有数字存入哈希表，实现 O(1) 的查询。
 * 2. 遍历集合中的每个数，通过判断 "num - 1 是否存在" 来确定该数是否为序列起点。
 * 3. 只有从起点出发，才开始向后累加计数。
 */

int solve() {
    int n;
    // NOI 竞赛中处理多组输入或读取 n
    if (!(cin >> n)) return 0;
    if (n == 0) return 0;

    vector<int> nums(n);
    unordered_set<int> num_set;
    
    // 关键优化点：预分配内存，减少 unordered_set 频繁扩容导致的 Rehash 耗时
    num_set.reserve(n); 

    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
        num_set.insert(nums[i]); // 自动去重
    }

    int longest_streak = 0;

    // 注意：遍历哈希表而不是原数组，可以减少重复元素的无效判断
    for (int num : num_set) {
        // 关键逻辑：寻找序列的“绝对起点”
        // 如果 num - 1 在集合中，说明 num 肯定不是起点，跳过它。
        // 只有 num 是起点时，才进入下面的 while 循环。
        if (num_set.find(num - 1) == num_set.end()) {
            int current_num = num;
            int current_streak = 1;

            // 只有作为起点的数才会触发后续查找
            while (num_set.find(current_num + 1) != num_set.end()) {
                current_num += 1;
                current_streak += 1;
            }

            // 更新全局最大长度
            longest_streak = max(longest_streak, current_streak);
        }
    }

    return longest_streak;
}

int main() {
    // NOI 竞赛提速必备：关闭 I/O 同步流
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cout << solve() << endl;

    return 0;
}

二、 复杂度分析思考过程

1. 时间复杂度：均摊 $O(n)$

• 第一步（插入）：将 $n$ 个数字插入 unordered_set，期望时间为 $O(n)$。
• 第二步（遍历与计数）：
  • 外部 for 循环遍历了集合中的每个元素，共执行 $n$ 次。
  • 内部 while 循环看起来很吓人，但由于我们加了 !num_set.count(num - 1) 的判断，每个数字只会在作为序列的一员时被 while 循环访问一次。
  • 例如：对于序列 1, 2, 3, 4，只有在处理 1 的时候会进入 while 遍历 2, 3, 4。当处理到 2, 3, 4 时，因为它们前面都有数字，会直接被 if 过滤掉。
• 结论：总的操作次数是 $n + n = 2n$，时间复杂度为 $O(n)$。

2. 空间复杂度：$O(n)$

• 推导：需要使用哈希表存储所有的数字。在 $n=10^5$ 的量级下，约占用几兆字节内存。
• 结论：在 NOI 256MB 的限制下非常安全。

三、 考场优化建议与易错点

1. 哈希冲突风险（防 Hack）： 在某些极端测试点下，unordered_set 的哈希函数可能被恶意构造的数据触发大量冲突，导致复杂度退化到 $O(n^2)$。

   • 建议：在真正的 NOI 考场上，若担心被卡，可以使用 std::unordered_set<int, custom_hash> 自定义哈希函数（加入随机扰动时间戳）。

2. 避免 std::set： std::set 底层是红黑树，查询是 $O(\log n)$。如果使用它，总时间复杂度会变成 $O(n \log n)$。在 $10^5$ 规模且时限紧的情况下，可能会丢掉 10-20 分。

3. 使用 reserve 预热： 哈希表在元素增多时会自动扩容。通过 num_set.reserve(n) 提前申请足够的桶（bucket），可以显著减少程序运行常数，这是抢时限的小窍门。

4. I/O 性能： 如果 $n$ 很大，输出一定要用 \n 而不是 endl，因为 endl 会强制刷新输出缓冲区，极其耗时。

四、 读题关键词总结

在 NOI 考场上，看到以下特征要迅速反应：

• “未排序” + “线性时间 / O(n)”：这是最明显的信号，提示你不能排序，必须用哈希表。
• “连续”：在数值空间中连续，意味着 $x$ 后面必跟着 $x+1$。
• “不要求序列元素在原数组中连续”：这告诉我们原数组的顺序是没用的信息，进一步锁定了“数值集合”处理法。

教练寄语： 这道题的精髓在于**“起点的判定”**。通过一个简单的 num-1 检查，把一个看似 $O(n^2)$ 的暴力搜索剪枝成了均摊 $O(n)$ 的神级算法。这种对计算冗余的剔除，就是算法竞赛的魅力所在。加油！