你好，同学。作为教练，我为你整理了这道题的 NOIP 竞赛级标准程序。

在 NOI 竞赛中，追求的不仅是“能跑通”，更是“在大数据量下的稳健与高效”。虽然本题规模 $10^4$ 暴力可过，但我们必须掌握 $O(n)$ 的最优解法，以应对未来可能出现的 $10^5$ 甚至 $10^6$ 级别的数据。

一、 两数之和 标准题解 (C++14)

#include <iostream>
#include <vector>
#include <unordered_map> // NOI 竞赛中常用哈希表

using namespace std;

/**
 * 核心逻辑：一遍哈希扫描法
 * 1. 扫描到一个数 x 时，我们目标明确：寻找 target - x。
 * 2. 如果哈希表里已经存了 target - x，说明匹配成功。
 * 3. 如果没存，就把 x 和它的下标存进去，给后面的数“当另一半”。
 */

void solve() {
    int n;
    long long target; // 使用 long long 防止 target 计算溢出
    if (!(cin >> n >> target)) return;

    vector<int> nums(n);
    // unordered_map 在 C++11/14 中是基于哈希表实现的，查找期望时间为 O(1)
    // key: 数值, value: 对应的下标
    unordered_map<int, int> dic;

    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    for (int i = 0; i < n; ++i) {
        int complement = target - nums[i];

        // 易错点：必须在将当前数放入哈希表之前查找
        // 这样可以自动避免“同一个元素重复出现”的问题
        if (dic.count(complement)) {
            // 找到了！输出存下的下标和当前下标
            cout << dic[complement] << " " << i << endl;
            return; // 题目保证只有一个答案，直接结束
        }

        // 如果没找到，将当前数值及其下标存入哈希表
        dic[nums[i]] = i;
    }
}

int main() {
    // NOI 竞赛必备优化：加速 I/O。在大规模数据输入时，比 scanf 还要快。
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

    return 0;
}

二、 复杂度分析思考过程

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

• 推导过程：
  • 我们只对数组进行了一次线性遍历（for 循环 $n$ 次）。
  • 在循环内部，unordered_map 的查找（count）和插入（operator[]）操作在平均情况下的时间复杂度均为 $O(1)$。
• 结论：总时间复杂度为 $O(n)$。在 $n=10^4$ 甚至 $10^5$ 时，该程序都能在数毫秒内完成。

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

• 推导过程：
  • 我们需要一个哈希表来存储遍历过的元素。在最坏情况下（即最后两个数才匹配成功），哈希表会存储 $n-1$ 个元素。
• 结论：额外空间复杂度为 $O(n)$。在 NOI 256MB 的内存限制下，存储 $10^5$ 个 int 仅占用约 2-4MB，非常安全。

三、 时间复杂度优化建议

虽然上述代码已经是期望 $O(n)$ 的最优解，但在 NOI 竞赛中，如果遇到极端的“哈希冲突测试数据”（Anti-Hash Test Cases），unordered_map 的效率可能会退化到 $O(n^2)$。以下是进阶优化建议：

1. 预分配空间 (Reserve)： 如果你知道数组长度 $n$，可以调用 dic.reserve(n)。这能减少哈希表动态扩容时的内存分配次数，显著提升速度。

2. 防御性哈希 (Custom Hash)： 为了防止出题人故意构造让哈希冲突的数据，可以手写一个简单的随机扰动函数给哈希表。

3. 排序 + 双指针方案 ($O(n \log n)$)： 如果内存限制极其严苛，不允许使用哈希表，可以先对数组进行排序，然后使用左、右两个指针向中间靠拢。

   • 优点：不需要额外哈希空间，且时间复杂度非常稳定。
   • 缺点：排序后原下标会乱，需要使用 pair<int, int> 同时存储数值和原下标。

4. 快读 (Fast I/O)： 如果 $n$ 达到 $10^6$ 级别，可以使用 getchar() 手写读取函数。

教练点评： 这道题是学习**“利用额外空间换取查找速度”**的入门教科书。在考场上，请务必注意 $target - nums[i]$ 的计算是否会超出 int 范围，以及哈希表容器是否正确使用。加油！