哈希表 开篇 set map操作

当我们遇到了要快速判断一个元素是否出现集合里的时候就要考虑哈希法。遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法哈希表定义一种实现关联数组的数据结构将键映射到值。核心机制哈希函数将键转换为数组中的索引。关键操作插入、删除、查找平均时间复杂度为 O(1)。C 标准库提供了两种哈希表容器unordered_map键值对存键和对应的值比如unordered_mapstring, int map;unordered_set只有键只存键判断是否存在比如unordered_setint set;其他的set map什么的底层是红黑树不是哈希表一、头文件固定cpp#include unordered_map #include unordered_set using namespace std;二、定义创建cppunordered_mapint, string mp; // 空map unordered_mapint, string mp2 {{1,a},{2,b}}; // 带初值 unordered_setint st; // 空set unordered_setint st2 {1,2,3}; // 带初值 unordered_setListNode* visited; // 指针作键链表题三、增删改查操作unordered_map操作it-first 取键 1234 keyit-second 取值 abcd value操作代码增插入mp[3] c;或mp.insert({4, d});查安全auto it mp.find(3); if (it ! mp.end()) { cout it-second; }改修改mp[3] C;key存在则覆盖删删除mp.erase(3);unordered_set操作操作代码增st.insert(5);查if (st.find(5) ! st.end()) { ... }改无直接改先删后插st.erase(5); st.insert(10);删st.erase(5);做哈希表部分的第一道题242.有效的字母异位词力扣题目链接class Solution { public: bool isAnagram(string s, string t) { int a[26]{0}; //int b[26]{0}; for(int i0;is.size();i){ a[s[i]-a];//我一开始在回忆是减32还是减多少原来只用减a就行。 } for(int i0;it.size();i){ //b[t[i]-a]; a[t[i]-a]--; } //if(a[26]b[26])是错误的写法哦 for(int i0;i26;i){ if(a[i]!0)return false; } return true; } };这里面的“通过对同一个数组加加减减判定两个数组是否相同”的思路特别值得学习加减后等于零就说明他们相等下一道题都思路也一模一样。383. 赎金信力扣题目链接class Solution { public: bool canConstruct(string ransomNote, string magazine) { int a[26]{0}; for(int i0;imagazine.size();i){ a[magazine[i]-a]; } bool flagtrue; for(int i0;iransomNote.size();i){ a[ransomNote[i]-a]--; if(a[ransomNote[i]-a]0){ flagfalse; break; } } return flag; } };