第九课《神秘数字配对——Two Sum问题》一、国王的神秘宝箱1、一天。程序王国举行寻宝大赛。 奖品是一只传说中的黄金宝箱。2、宝箱上写着一句话只有找到两个数字 它们的和等于目标数字 宝箱才会打开3、例如宝石数字2 7 11 15目标数字94、国王问哪两个数字加起来等于95、小朋友们很快发现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 i0;in;i) { for(int ji1;jn;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_setint 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_setint 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() { vectorint a{2,7,11,15}; int target9; unordered_setint 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 target93、答案0 14、因为a[0]2 a[1]75、这时候unordered_mapint,int就登场了。十五、为什么要用unordered_map1、因为我们不仅想知道数字存在吗2、还想知道数字在哪里3、于是unordered_mapint,int mp;1表示数字 → 下标2例如2 → 0 7 → 1 11 → 2十六、经典模板unordered_mapint,int mp; for(int i0;in;i) { int needtarget-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_setint 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全部串联起来成为真正的哈希表小勇士