GESP7级C++考试语法知识（四、哈希表（9、Two Sum问题）

第九课：《神秘数字配对——Two Sum问题》

一、国王的神秘宝箱

1、一天。

程序王国举行寻宝大赛。

🏆 奖品是一只传说中的黄金宝箱。

2、宝箱上写着一句话：

只有找到两个数字， 它们的和等于目标数字， 宝箱才会打开！

3、例如：

宝石数字：

2 7 11 15

目标数字：

9

4、国王问：

哪两个数字加起来等于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 + 15

4、这是：

枚举所有组合

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、假设目标值：

9

2、现在看到数字：

2

3、国王问：

还缺多少？

4、答案：

9 - 2 = 7

5、也就是说：

如果7出现过 那么： 2 + 7 = 9

6、再看：

11

7、还缺：

9 - 11 = -2

8、如果：

-2存在

就成功。

八、核心思想

1、以前：

找两个数字

2、现在：

看到一个数字x 计算： target - x

3、然后问：

这个数字存在吗？

这不正是：

哈希表最擅长的事情吗？

九、哈希表登场

1、智慧大臣拿出：

unordered_set<int> s;

2、作用：

记录已经见过的数字

十、一步一步找答案

1、数组：

2 7 11 15

2、目标：

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=9

3、答案：

0 1

4、因为：

a[0]=2 a[1]=7

5、这时候：

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

全部串联起来，

成为真正的哈希表小勇士！🏆🚀