📱

哈希表应用：C++ 自带的「超级字典」，拿来就用

不用自己造抽屉——unordered_map 是「词→词数」的超级字典，unordered_set 是「见过没见过」的 O(1) 雷达。

💡 打个比方：手机里的超级字典

手机通讯录不用一格格翻：输入名字直接弹出来。C++ 的 unordered_map 就是这样的超级字典：左边存 key（单词），右边存 value（次数），查一个、记一个都是「一步到位」；unordered_set 是它的简化版——只记「见过谁」，用来 O(1) 判断「是否出现过」。

📖 术语小抄：unordered_map = 无序的键值字典（key→value），平均 O(1)；unordered_set = 无序集合，只存 key，平均 O(1) 判「在不在」；mp[key]++ = key 不存在时自动新建（初始 0）再 +1；set.count(x) = x 在不在集合里（1/0）；set.insert(x) = 把 x 放进去（已有就不重复放）；Two Sum = 两数之和（找两数相加 = 目标值）。

🖼️ 大图看明白：超级字典 + 词频 + Two Sum

🧩 子任务 1：unordered_map 入门——统计单词词频

🎯 小目标：会用 mp[w]++ 统计词频，能手推字典每一步的变化，知道「key 不存在时自动新建」这个魔法。

// 任务：统计一串单词里每个词出现几次
// 工具：unordered_map<string, int> freq;（左：单词，右：次数）
// 魔法：freq[w]++ —— w 不在字典里？自动新建（次数从 0 开始），再 +1
//
// 输入单词：apple banana apple cherry banana apple
// 手推字典的变化：
//   apple  → {}                          → {apple:1}
//   banana → {apple:1}                  → {apple:1, banana:1}
//   apple  → {apple:1, banana:1}        → {apple:2, banana:1}
//   banana → {apple:2, banana:1, cherry:1} → {apple:2, banana:2, cherry:1}
//   apple  → {apple:2, banana:2, cherry:1} → {apple:3, banana:2, cherry:1}
// 最终：apple 3 次、banana 2 次、cherry 1 次（共 6 个词）

✅ 小检查：① freq[w]++ 对「第一次出现的 w」做了什么？② 如果单词换成「cat dog cat cat」，最终字典是什么？③ 怎么输出每个词和它的次数？

看看答案

① 自动新建条目（次数 = 0）再 +1——所以第一次出现就是 1。这正是 mp[key] 的「访问即创建」行为。 ② {cat:3, dog:1}。 ③ 用 for 遍历字典：for (auto &p : freq) cout << p.first << " " << p.second << endl;（p.first 是 key，p.second 是 value）。

⚠️ 易错：① unordered_map 的遍历顺序是乱的（不是按输入顺序、也不是按字母序）——题目要求「按出现顺序/按字母序输出」时，要另想招（记下出现顺序，或换 map）；② key 用 string 时别忘 #include 和 using namespace std。

🧩 子任务 2：unordered_set——去重和「见过没见过」O(1) 雷达

🎯 小目标：会用 set 做去重（保持第一次出现的顺序输出）和成员判断。

// unordered_set：只存 key、不存 value 的「名单」
// 两个超能力：
//   seen.count(x)  → x 在名单里吗？返回 1/0（O(1)）
//   seen.insert(x) → 把 x 加进名单（已经有了就不重复加）
//
// 应用 1：去重（保留每个数第一次出现的位置）
//   输入：3 1 4 1 5 9 2 6 5
//   seen 空
//   3 → count=0 → 输出 3，insert 3　seen={3}
//   1 → count=0 → 输出 1，insert 1　seen={3,1}
//   4 → count=0 → 输出 4，insert 4　seen={3,1,4}
//   1 → count=1 → 跳过（见过）
//   5 → count=0 → 输出 5，insert 5　seen={3,1,4,5}
//   9 → 输出 9，insert　2 → 输出 2，insert　6 → 输出 6，insert
//   5 → count=1 → 跳过
//   结果：3 1 4 5 9 2 6（重复的 1、5 只留第一次）

✅ 小检查：① 「判断 x 是否出现过」用数组下标、链表、unordered_set 分别多快？② 去重输出为什么是 3 1 4 5 9 2 6 而不是 1 2 3 4 5 6 9？③ seen.count(x) 的返回值是什么？

看看答案

① 数组：O(1) 但要求 x 是范围小的非负整数；链表：O(n) 逐个比；unordered_set：平均 O(1)，x 多大都行。 ② 去重代码是「按输入顺序扫一遍，谁第一次出现就先输出谁」——set 只负责判重，不改变输出顺序（set 自己的遍历顺序才是乱的，这里没遍历 set）。 ③ 返回 1（在）或 0（不在），可以直接写 if (seen.count(x))。

⚠️ 易错：① 把「set 遍历顺序是乱的」当成「按 set 输出就是去重后的有序结果」——要按原顺序去重，必须扫原数组 + set 判重；② insert 之后再用 count 判断——顺序反了，重复的就被放出去了（先 count 后 insert）。

🧩 子任务 3：Two Sum——一次遍历 + set 找补数

🎯 小目标：掌握「边扫边存」的 Two Sum 套路：对每个 x，问 seen 里有没有 9-x；能手推找出全部解。

// 两数之和：nums 里找两数相加 = target（这里 target = 9）
// 笨办法：两重循环 O(n²)，n = 10 万 → 100 亿次，太慢
// 快办法：一次遍历 + seen 集合
//   扫到 x 时，补数 need = target - x
//   问：seen（前面扫过的数）里有 need 吗？
//     有 → 找到一对 (need, x)！
//     没有 → 把 x 存进 seen，继续扫
//
// nums = [2, 7, 4, 5, 11, 15]，target = 9，手推：
//   x=2：need=7，seen={} → 没有 → seen={2}
//   x=7：need=2，2 ∈ seen → 命中！(2, 7) → seen={2,7}
//   x=4：need=5，seen={2,7} → 没有 → seen={2,7,4}
//   x=5：need=4，4 ∈ seen → 命中！(4, 5) → seen={2,7,4,5}
//   x=11：need=-2 → 没有 → seen={2,7,4,5,11}
//   x=15：need=-6 → 没有 → seen={2,7,4,5,11,15}
// 全部解：(2, 7) 和 (4, 5) —— 共 2 对，一次遍历 O(n) 找完
// 为什么每对只被找到一次？后面那个数问「need 在前面吗」，
//   前面的数不会回头再问——每个有序对恰好问一次。

✅ 小检查：① 这个办法为什么是 O(n)？② 如果 nums = [1, 2, 3, 4, 5]，target = 6，有哪些解？③ 为什么不能「先把所有数 insert 进 set 再遍历」？（提示：x = 3, target = 6 时）

看看答案

① 只扫一遍：每个 x 做 O(1) 的 count + O(1) 的 insert，共 n 次 → O(n)。 ② 扫 1：need=5 不在 → {1}；扫 2：need=4 不在 → {1,2}；扫 3：need=3 不在 → {1,2,3}；扫 4：need=2 在 → (2,4)；扫 5：need=1 在 → (1,5)。解：(2,4)、(1,5) 两对。（3+3=6 但只有一个 3，不算。） ③ 先全存再遍历，扫到 x=3 时 seen 里有 3（自己），会误报「3+3=6」——但数组里只有一个 3。边扫边存保证 need 一定在 x 前面，不会拿自己凑对。

⚠️ 易错：① 顺序必须是「先查 need，再 insert x」——反过来就可能出现 x + x 的假解（只有一个 x 时）；② 要「全部解」就继续扫完整个数组，找到一对不要 break；③ 输出顺序：先 found 的先输出（本题 2+7 在 4+5 前面）。

🧩 子任务 4：unordered_map vs map——O(1) 还是 O(log n)？要不要「有序」

🎯 小目标：分清 unordered_map 和 map 的速度与顺序差异，会按需求选。

// 两个「字典」兄弟：
//   unordered_map：底层是哈希表 → 查/插平均 O(1)，但 key 顺序是乱的
//   map：底层是二叉搜索树（红黑树）→ 查/插 O(log n)，但 key 永远从小到大排好
//
// 怎么选？看题目要不要「按 key 有序输出」：
//   只要快（判重、计数、Two Sum）        → unordered_map / unordered_set
//   要按 key 从小到大输出 / 要「最大 key」「前驱后继」→ map / set
//
// 账怎么算（n = 10 万）：
//   10 万次查找：
//     unordered_map ≈ 10 万 × O(1) ≈ 10 万次比较
//     map          ≈ 10 万 × O(log n) ≈ 10 万 × 17 ≈ 170 万次比较
//   平时 unordered 快 10 几倍；但 map 给你「有序」这个 unordered 没有的本事
//   （map 的 lower_bound / upper_bound 也能 O(log n) 找位置）
// 一句话：要速度选 unordered，要顺序选 map，两者 API 几乎一样，换个头就能用

✅ 小检查：① 统计词频后要求「按单词字母序输出」，用哪个？② 只做「这个数见过没」判断，用哪个？③ n = 10 万时，map 一次查找大约比较多少次？为什么是 17？

看看答案

① map（或 unordered_map 存完 + 把结果排序输出，两种都行；直接 map 最省事）。 ② unordered_set——平均 O(1)，不需要顺序。 ③ log₂(100000) ≈ 17 次：树高约 log n 层，每层比较一次 key 走左还是走右，17 层就到。

⚠️ 易错：① 看到「有序输出」需求还在用 unordered_map 遍历——顺序是乱的，WA；② 反过来，只要速度却用了 map，n 大时可能 TLE（超时）；③ 两者 API 几乎相同（mp[key]、mp.count、mp.size、for 遍历），切换 = 换一行声明。

💻 完整代码：词频统计 + Two Sum（输出所有解）

🎯 小目标：读懂「freq[w]++ 自动建条目」和「先查 need 再 insert」两段代码；对照输出。

// ① 词频统计 + ② Two Sum（输出所有解）
#include <bits/stdc++.h>
using namespace std;

int main() {
    // ① 词频：freq[w]++ —— w 不在就自动新建（0 起步）再 +1
    vector<string> words = {"apple","banana","apple","cherry","banana","apple"};
    unordered_map<string,int> freq;
    for (auto &w : words) freq[w]++;
    for (auto &p : freq)                 // 遍历：p.first=词，p.second=次数
        cout << p.first << " " << p.second << endl;
    // 输出（顺序随机）：apple 3 / banana 2 / cherry 1

    // ② Two Sum：target = 9，边扫边存，输出所有解
    vector<int> nums = {2, 7, 4, 5, 11, 15};
    int target = 9;
    unordered_set<int> seen;             // 「前面扫过的数」名单
    for (int x : nums) {
        int need = target - x;           // 补数
        if (seen.count(need))            // 前面有人和 x 凑成 target
            cout << need << " + " << x << " = " << target << endl;
        seen.insert(x);                  // 先查后存（顺序不能反！）
    }
    // 输出：2 + 7 = 9
    //       4 + 5 = 9
    return 0;
}

// 运行对照（②）：
//   x=2：seen 无 7 → 存 2
//   x=7：seen 有 2 → 输出 2 + 7 = 9 → 存 7
//   x=4：seen 无 5 → 存 4
//   x=5：seen 有 4 → 输出 4 + 5 = 9 → 存 5
//   x=11、15：need = -2、-6，seen 都没有 → 只存不输出

✋ 你来试试

第 1 题：用 freq[w]++ 统计 ["cat","dog","cat","fish","cat"]，最终字典是什么？

{cat:3, dog:1, fish:1}——cat 出现 3 次（每次 +1），dog 和 fish 各 1 次。输出顺序随机，但「词→次数」的对应是准的。

第 2 题：对 5 3 5 8 3 8 5 做「按原顺序去重」，输出什么？seen 最后是什么？

输出 5 3 8（每个数只留第一次出现的位置）；seen 最后 = {5, 3, 8}（3 个元素，重复的 insert 不生效）。

第 3 题：nums = [3, 3, 4, 7]，target = 6。「边扫边存」能找到几对？是哪对？

1 对：(3, 3)。手推：x=3 时 need=3，seen 空 → 没找到，存 3；第二个 x=3 时 need=3，seen 里有 3 → 命中 (3,3)。两个 3 一前一后，「先查后存」恰好能凑对；如果只有一个 3，就不会误报。

第 4 题（加餐）：nums 有 200000 个数，找所有和为 target 的数对。两重循环最坏大约多少次？「边扫边存」多少次？

两重循环：200000 × 200000 / 2 ≈ 2×10¹⁰（200 亿）次，普通评测会超时；边扫边存：每个数 1 次 count + 1 次 insert，共 200000 次（O(n)），飞快。这就是「哈希表换掉一重循环」的典型用法。

🎯 一句话记住：C++ 自带超级字典——unordered_map[key]++ 自动建条目、O(1) 计数；unordered_set 做 O(1) 去重和「见过没见过」雷达（先 count 后 insert 保原序去重）；Two Sum = 边扫边存：每个 x 先问 seen 里有没有 target-x、再把自己存进去，一次 O(n) 遍历找出所有解；要速度选 unordered（O(1)），要「按 key 有序输出」换 map（O(log n)，key 自动排好）。

← 上一课：哈希表基础回总索引 →