Day3 记忆内容：map set 高频操作
以下是 第三天 的详细学习内容，聚焦 map和set的高效应用，重点突破查找类题型和去重逻辑，助你提升代码效率！
📚 Day3 记忆内容：map & set 高频操作
1. map 核心操作（手写3遍）
// 初始化
map<string, int> mp; // 有序（按key升序）
unordered_map<string, int> ump; // 无序（哈希表，查询O(1)）// 关键API
mp["apple"] = 5; // 插入/修改（若key不存在则创建）
mp.insert({"banana", 3}); // 插入（若key存在则不覆盖）
auto it = mp.find("apple"); // 返回迭代器（未找到返回mp.end()）
mp.erase(it); // 通过迭代器删除
mp.count("apple"); // 返回存在次数（0或1）
mp.lower_bound(50); // 返回首个≥key的迭代器（有序map特有）// 遍历（C++17风格）
for (auto& [key, value] : mp) { cout << key << ":" << value << endl;
}
2. set 核心操作（手写3遍）
// 初始化
set<int> s; // 有序集合（元素唯一）
unordered_set<int> us; // 无序集合（哈希实现）// 关键API
s.insert(10); // 插入元素
s.erase(10); // 删除元素
auto it = s.find(5); // 查找元素
s.count(5); // 是否存在
s.lower_bound(8); // 返回首个≥8的迭代器（有序set特有）
3. 易错点总结
map的operator[]访问不存在的key时会自动插入（value默认初始化）- 遍历时删除元素会导致迭代器失效，需先保存后删除
unordered_map的 key 需要支持哈希函数（自定义类型需特化std::hash）
💻 Day3 练习题（每题限时25分钟）
题目1：统计单词频率（map应用）
题目描述
输入一段英文文本（不含标点），统计每个单词的出现频率（区分大小写）。
示例输入/输出
输入："Apple banana apple Apple"
输出：Apple:3, banana:1, apple:1
关键思路
- 用
map<string, int>存储单词和频率 - 遍历分割后的单词，更新map
参考代码
#include <sstream>map<string, int> wordCount(const string& text) {map<string, int> freq;istringstream iss(text);string word;while (iss >> word) {freq[word]++; // 自动处理不存在的情况}return freq;
}
题目2：两数之和（unordered_map应用）
题目描述
给定整数数组 nums 和目标值 target，返回两数之和等于目标值的下标（假设答案唯一）。
示例输入/输出
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
关键思路
- 用
unordered_map存储值到索引的映射 - 遍历时检查
target - num是否已存在
参考代码
vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> val2idx;for (int i = 0; i < nums.size(); i++) {int complement = target - nums[i];if (val2idx.count(complement)) {return {val2idx[complement], i};}val2idx[nums[i]] = i; // 后插入当前数，避免重复使用同一元素}return {};
}
📝 今日卡壳点记录表
| 卡壳位置 | 错误原因 | 修正方法 |
|---|---|---|
误用 map.insert 覆盖值 | 未判断直接插入导致旧值丢失 | 先用 find 检查是否存在 |
| 哈希表遍历顺序问题 | 误以为 unordered_map 有序 | 需明确无序特性 |
| 未处理单词大小写差异 | 题目要求区分大小写 | 保持原词，不转小写 |
⏰ 今日时间安排建议
18:00-18:30 手写 map/set 模板（重点区分有序和无序容器）
18:30-19:00 练习单词统计（注意istringstream的分割用法）
19:00-19:30 练习两数之和（体会哈希表O(1)查询优势）
19:30-20:00 对比参考代码，记录map插入逻辑的优化点
map和set是CSP中高频考点，尤其是两数之和这类哈希优化题！坚持手写，明天进入优先队列专题！ 🔥