算法刷题之哈希表

知识点

常见的哈希结构：数组、set、map

// 创建并初始化 unordered_set
unordered_set<int> set = {1, 2, 3, 4, 5};// 插入新元素
set.insert(6);// 检查元素是否存在
if (set.find(3) != set.end()) {cout << "3 is in the set" << endl;
}// 删除元素
set.erase(3);// 检查集合大小
cout << "Set size: " << set.size() << endl;// 检查集合是否为空
if (set.empty()) {cout << "The set is empty." << endl;
}// 遍历集合
for (int num : set) {cout << " " << num;
}// 计数元素出现次数（对于 unordered_set 总是 1 或 0）
cout << "Count of 4 in the set: " << set.count(4) << endl;// 清空集合
set.clear();

// 创建并初始化 unordered_map
unordered_map<int, string> um = {{1, "one"},{2, "two"},{3, "three"}
};// 插入新元素
um.insert({4, "four"});
um[5] = "five"; // 使用下标操作符进行插入或赋值// 访问元素
cout << "Value for key 1: " << um[1] << endl;// 查找元素
auto it = um.find(3);
if (it != um.end()) {cout << "Found: " << it->second << endl;
}// 删除元素
um.erase(3); // 删除键为3的元素
um.clear(); // 清空所有元素// 获取元素数量
cout << "Size after clear: " << um.size() << endl;// 检查是否为空
cout << "Is the map empty? " << (um.empty() ? "Yes" : "No") << endl;// 遍历元素
for (const auto& pair : um) {cout << pair.first << " => " << pair.second << endl;
}// 使用 emplace 插入元素
um.emplace(3, "three");// 获取迭代器并遍历
auto beginIt = um.begin();
auto endIt = um.end();
for (auto it = beginIt; it != endIt; ++it) {cout << it->first << " => " << it->second << endl;
}// 更新元素
um[1] = "ONE"; // 更新键为1的元素的值

哈希的核心思想是把需要的数据提前计算并存储，以空间换时间

例题

383. 赎金信 - 力扣（LeetCode）

bool canConstruct(string ransomNote, string magazine) {int a[26], b[26];for(int i = 0; i < ransomNote.size(); i ++){a[ransomNote[i] - 'a'] ++;}for(int i = 0; i < magazine.size(); i ++){b[magazine[i] - 'a'] ++;}for(int i = 0; i < 26; i++){if(a[i] > b[i]) return false;}return true;
}