第九课：《神秘数字配对——Two Sum问题》
一、国王的神秘宝箱
1、一天。
程序王国举行寻宝大赛。
🏆 奖品是一只传说中的黄金宝箱。
2、宝箱上写着一句话：
只有找到两个数字， 它们的和等于目标数字， 宝箱才会打开！3、例如：
宝石数字：
2 7 11 15目标数字：
94、国王问：
哪两个数字加起来等于9？
5、小朋友们很快发现：
2 + 7 = 9宝箱打开！
🎉🎉🎉
二、什么是 Two Sum 问题？
Two Sum（两数之和）是算法界最经典的问题之一。
题目通常长这样：
给定数组：
2 7 11 15目标值：
9问：
是否存在两个数字， 它们的和等于9？答案：
2 和 7三、最容易想到的方法
1、小胖说：
这还不简单？
2、把所有数字两两配对。
数组：
2 7 11 15检查：
2 + 7 = 9找到！
3、如果没找到呢？
继续：
2 + 11 2 + 15 7 + 11 7 + 15 11 + 154、这是：
枚举所有组合
5、代码：
for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(a[i]+a[j]==target) { cout<<"找到"; } } }四、小数据没问题
1、假设：
10个数字2、比较次数：
大约45次很轻松。
五、大数据就惨了
1、假设：
100000个数字2、比较次数：
100000 × 100000约：
100亿次电脑：
😭😭😭
六、智慧大臣发现秘密
智慧大臣观察了一会儿。
突然说：
我们为什么要找两个数字？
其实只需要找一个数字！
国王：
😲？？？
七、神奇公式出现
1、假设目标值：
92、现在看到数字：
23、国王问：
还缺多少？
4、答案：
9 - 2 = 75、也就是说：
如果7出现过 那么： 2 + 7 = 96、再看：
117、还缺：
9 - 11 = -28、如果：
-2存在就成功。
八、核心思想
1、以前：
找两个数字2、现在：
看到一个数字x 计算： target - x3、然后问：
这个数字存在吗？这不正是：
哈希表最擅长的事情吗？
九、哈希表登场
1、智慧大臣拿出：
unordered_set<int> s;2、作用：
记录已经见过的数字十、一步一步找答案
1、数组：
2 7 11 152、目标：
9开始。
第一个数字
2计算：
9 - 2 = 7检查：
s.count(7)结果：
0说明：
7还没出现登记：
s.insert(2);仓库：
{2}第二个数字
7计算：
9 - 7 = 2检查：
s.count(2)结果：
1说明：
2已经出现过找到答案：
2 + 7 = 9成功！
🎉🎉🎉
十一、神级模板
1、这是经典代码：
unordered_set<int> s; for(int x : a) { if(s.count(target - x)) { cout<<"找到"; } s.insert(x); }2、代码解释：
看到数字x 先找伙伴 伙伴是： target - x 如果伙伴已经出现 答案找到 同时登记自己十二、完整程序
#include <iostream> #include <vector> #include <unordered_set> using namespace std; int main() { vector<int> a={2,7,11,15}; int target=9; unordered_set<int> s; for(int x:a) { if(s.count(target-x)) { cout<<"找到数字对：" <<x <<" 和 " <<target-x <<endl; return 0; } s.insert(x); } cout<<"未找到"; return 0; }输出：
找到数字对：7 和 2十三、为什么这么快？
1、普通方法：
两层循环2、复杂度：
O(n²)3、哈希表方法：
每个数字检查一次（1）每次：
s.count()（2）平均：
O(1)（3）总复杂度：
O(n)速度提升巨大！
十四、升级版：输出下标
1、很多比赛题目要求：
输出数字的位置2、例如：
2 7 11 15 target=93、答案：
0 14、因为：
a[0]=2 a[1]=75、这时候：
unordered_map<int,int>就登场了。
十五、为什么要用unordered_map？
1、因为我们不仅想知道：
数字存在吗2、还想知道：
数字在哪里3、于是：
unordered_map<int,int> mp;（1）表示：
数字 → 下标（2）例如：
2 → 0 7 → 1 11 → 2十六、经典模板
unordered_map<int,int> mp; for(int i=0;i<n;i++) { int need=target-a[i]; if(mp.count(need)) { cout << mp[need] << " " << i; } mp[a[i]]=i; }这是著名的：
Two Sum 最优解
十七、例题挑战
数组：
3 8 2 5目标：
10开始：
看到：
3需要：
7不存在。
登记：
3看到：
8需要：
2不存在。
登记：
8看到：
2需要：
8存在！
答案：
8 + 2 = 10十八、再来一道
数组：
1 4 6 9目标：
13看到：
1需要：
12不存在。
看到：
4需要：
9不存在。
看到：
6需要：
7不存在。
看到：
9需要：
4存在！
答案：
4 + 9 = 13十九、哈希表思想的本质
1、有的同学学完会发现：
以前思路：
找两个数字很难。
2、哈希表思路：
看到一个数字 寻找它需要的伙伴很简单。
3、这就是：
化复杂为简单
也是哈希表迷人的地方。
本课总结
1、今天学习了哈希表最著名的问题：
Two Sum（两数之和）
2、核心公式：
need = target - x;3、核心判断：
if(s.count(need))4、核心模板：
unordered_set<int> s; for(int x:a) { if(s.count(target-x)) { cout<<"找到"; } s.insert(x); }5、时间复杂度：
O(n)6、比暴力枚举：
O(n²)快得多！
魔法口诀
目标数字记心中， 看到数字找搭档。 搭档是谁别乱猜， target减它就出来。 哈希仓库查一下， 伙伴出现马上答。 Two Sum最经典， 哈希表把难题化简单！下一课预告
下一课我们将进入哈希表综合实战：
《哈希王国终极挑战——综合应用训练》
你将把学过的：
✅ 统计次数
✅ 判断存在
✅ 查重问题
✅ Two Sum
全部串联起来，
成为真正的哈希表小勇士！🏆🚀
