你好，同学！欢迎来到 NOI 数据结构与算法专题训练。

今天我们要攻克的是算法入门中的经典——两数之和。在竞赛中，虽然这道题看起来简单，但它蕴含了“空间换时间”和“哈希查找”这两个极其重要的 NOI 基础思想。

一、 预备知识点

在动手之前，请确保你已经掌握：

1. 数组（Array）：基本的线性存储结构。
2. 时间复杂度分析：理解 $O(n^2)$ 与 $O(n)$ 的性能差异。
3. 哈希表（Hash Table）：在 C++ STL 中通常使用 std::unordered_map。
   • count() 或 find()：检查某个键是否存在（期望时间 $O(1)$）。
   • insert 或 operator[]：插入键值对。

二、 NOI 竞赛题目描述

题目名称：两数之和 (Two Sum) 时间限制：1.0s 内存限制：256MB

【问题描述】 给定一个整数数组 $nums$ 和一个目标值 $target$，请你在该数组中找出和为目标值 $target$ 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

【输入格式】 输入共两行。 第一行包含两个整数 $n$ 和 $target$，分别表示数组长度和目标值。 第二行包含 $n$ 个整数，表示数组 $nums$。

【输出格式】 输出两个整数，表示满足条件的数组下标，以空格分隔。

【样例输入】

4 9
2 7 11 15

【样例输出】

0 1

【数据规模与约定】

• $2 \le n \le 10^4$
• $-10^9 \le nums[i] \le 10^9$
• $-10^9 \le target \le 10^9$
• 保证仅存在一个有效答案。

三、 启发式引导：草稿纸上的推演过程

请拿出草稿纸，随我一起模拟思维的进化。

1. 暴力思维：穷举法

• 动作：像在班级里找两个身高加起来等于 300 厘米的同学。你先拉住甲，然后让剩下的人一个个过来比。
• 复杂度分析：
  • 时间：$O(n^2)$。两层 for 循环，对于 $n=10^4$，计算量约 $10^8$，在 1s 边缘徘徊。
  • 空间：$O(1)$。
• 思考：有没有办法不让剩下的人“一个个过来比”？

2. 优化思维：寻找“另一半”

• 启发：当你确定了一个数 $x$ 时，你其实已经在找一个确定的数了：$y = target - x$。
• 动作：
  1. 准备一个本子（哈希表）。
  2. 遍历每个人。
  3. 问：“本子里有没有记过我要找的 $y$？”
  4. 如果有：成功，取出 $y$ 的编号，和当前编号一起上报。
  5. 如果没有：把自己的数值和编号记在本子上。
• 图形模拟：
  • nums: [2, 7, 11], target: 9
  • 遇到 2：找 7。本子空。在本子记下 {2: 0}。
  • 遇到 7：找 2。本子有 2！输出 0, 1。

四、 时间复杂度优化建议

• 暴力方案：$O(n^2)$。
• 哈希方案：$O(n)$。我们只遍历了一次数组，哈希查找是常数时间。
• NOI 考场提示：虽然 $n=10^4$ 暴力可能能过，但如果 $n$ 增加到 $10^5$，必须使用哈希表。注意在 C++ 中使用 unordered_map 而不是 map，因为前者基于哈希，后者基于红黑树（时间是 $O(\log n)$）。

五、 算法流程图（C++14 伪代码表示）

我们使用 Mermaid 语法展示哈希方案的逻辑。

graph TD
    Start(开始处理任务) --> InitMap(创建哈希表 Hash_Table)
    InitMap --> LoopBegin{遍历 i 从 0 到 n 减 1}
    LoopBegin -- 结束 --> NoFound(未找到匹配, 实际保证有解)
    LoopBegin -- 正在处理下标 i --> CalcDiff(计算补数 complement 等于 target 减去 nums_i)
    CalcDiff --> CheckExist{Hash_Table 中是否存在键为 complement?}
    
    CheckExist -- 是 --> Output(输出 Hash_Table_complement 和当前下标 i)
    CheckExist -- 否 --> Insert(将 nums_i 与 i 存入 Hash_Table)
    
    Insert --> LoopBegin
    Output --> End(程序结束)

六、 读题关键词总结

在 NOI 考场上，看到以下关键词要迅速反应：

1. “两个数”：通常暗示双指针或哈希表。
2. “和为目标值”：转化思想——如果确定 $A$，则 $B = target - A$。
3. “下标”：说明哈希表不仅要存数值，还要存对应的索引（Value）。
4. “只会对应一个答案”：这是一个强力的简化条件，意味着一旦找到，可以直接 return 或 exit，不用处理复杂的冲突。

教练寄语： 这道题的精髓在于“回头看”。我们在前进的过程中，把路过的信息存在哈希表里，让每一个新来的数都能快速查询过去的信息。这种“记忆化查找”的思想，是后续学习动态规划（DP）的重要基石。加油！