哈希表理论基础
C++ STL无序容器种类
和关联式容器一样，无序容器只是一类容器的统称，其包含有 4 个具体容器，分别为 unordered_map、unordered_multimap、unordered_set 以及 unordered_multiset。
表 1 对这 4 种无序容器的功能做了详细的介绍。
| 无序容器 | 功能 |
|---|---|
| unordered_map | 存储键值对 <key, value> 类型的元素，其中各个键值对键的值不允许重复，且该容器中存储的键值对是无序的。 |
| unordered_multimap | 和 unordered_map 唯一的区别在于，该容器允许存储多个键相同的键值对。 |
| unordered_set | 不再以键值对的形式存储数据，而是直接存储数据元素本身（当然也可以理解为，该容器存储的全部都是键 key 和值 value 相等的键值对，正因为它们相等，因此只存储 value 即可）。另外，该容器存储的元素不能重复，且容器内部存储的元素也是无序的。 |
| unordered_multiset | 和 unordered_set 唯一的区别在于，该容器允许存储值相同的元素。 |
unordered_map经典用法：
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main()
{
//创建空 umap 容器
unordered_map<string, string> umap;
//向 umap 容器添加新键值对
umap.emplace("Python教程", "http://c.biancheng.net/python/");
umap.emplace("Java教程", "http://c.biancheng.net/java/");
umap.emplace("Linux教程", "http://c.biancheng.net/linux/");
//输出 umap 存储键值对的数量
cout << "umap size = " << umap.size() << endl;
//使用迭代器输出 umap 容器存储的所有键值对
for (auto iter = umap.begin(); iter != umap.end(); ++iter) {
cout << iter->first << " " << iter->second << endl;
}
return 0;
}
在 unordered_map 容器模板中，提供了表 1 所示的成员方法，可用来获取指向指定位置的前向迭代器。
| 成员方法 | 功能 |
|---|---|
| begin() | 返回指向容器中第一个键值对的正向迭代器。 |
| end() | 返回指向容器中最后一个键值对之后位置的正向迭代器。 |
| cbegin() | 和 begin() 功能相同，只不过在其基础上增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对。 |
| cend() | 和 end() 功能相同，只不过在其基础上，增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对。 |
| find(key) | 查找以 key 为键的键值对，如果找到，则返回一个指向该键值对的正向迭代器；反之，则返回一个指向容器中最后一个键值对之后位置的迭代器（如果 end() 方法返回的迭代器）。 |
| equal_range(key) | 返回一个 pair 对象，其包含 2 个迭代器，用于表明当前容器中键为 key 的键值对所在的范围。 |
unordered_map相关成员迭代器的用法：
1 #include <iostream>
2 #include <string>
3 #include <unordered_map>
4 using namespace std;
5 int main()
6 {
7 //创建 umap 容器
8 unordered_map<string, string> umap{
9 {"Python教程","http://c.biancheng.net/python/"},
10 {"Java教程","http://c.biancheng.net/java/"},
11 {"Linux教程","http://c.biancheng.net/linux/"} };
12 cout << "umap 存储的键值对包括：" << endl;
13 //遍历输出 umap 容器中所有的键值对
14 for (auto iter = umap.begin(); iter != umap.end(); ++iter) {
15 cout << "<" << iter->first << ", " << iter->second << ">" << endl;
16 }
17 //获取指向指定键值对的前向迭代器
18 unordered_map<string, string>::iterator iter = umap.find("Java教程");
19 cout <<"umap.find(\"Java教程\") = " << "<" << iter->first << ", " << iter->second << ">" << endl;
20 return 0;
21 }
242. 有效的字母异位词
1 class Solution {
2 public:
3 bool isAnagram(string s, string t) {
4 //创建数组用于记录字母出现的次数
5 int res[26] = {0};
6 //记录s中每个字母出现的次数
7 for (int i = 0; i < s.size(); i++){
8 res[s[i] - 'a']++;
9 }
10 //减去t中每个字母出现的次数
11 for (int i = 0; i < t.size(); i++){
12 res[t[i] - 'a']--;
13 }
14 //判断每个字母的次数是否为零
15 for (int i = 0; i < 26; i++){
16 if (res[i] != 0){
17 return false;
18 }
19 }
20 return true;
21 }
22 };
349. 两个数组的交集
1 class Solution {
2 public:
3 vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
4 //创建result_set用于存放结果
5 unordered_set<int> result_set;
6 //创建num_set用于存放nums1
7 unordered_set<int> num_set(nums1.begin(),nums1.end());
8 //遍历nums2
9 for (int num : nums2){
10 //判断num是否在num_set中出现过
11 if (num_set.find(num) != num_set.end()){
12 result_set.insert(num);
13 }
14 }
15 //输出结果数组
16 return vector<int>(result_set.begin(), result_set.end());
17 }
18 };
202. 快乐数
1 class Solution {
2 public:
3 //创建函数用于n的各个位置的数字平方求和
4 int qiuhe(int n){
5 int sum = 0;
6 while(n != 0){
7 sum += (n % 10) * (n % 10);
8 n = n / 10;
9 }
10 return sum;
11 }
12
13 bool isHappy(int n) {
14 //创建unordered_set用于存储getSum(n)的结果
15 unordered_set<int> num_set;
16 int sum = qiuhe(n);
17 while(sum != 1){
18 sum = qiuhe(sum);
19 //如果unordered_set中不存在getSum(n),则将该数字存入结果集
20 if (num_set.find(sum) == num_set.end()){
21 num_set.insert(sum);
22 //存在则说明结果集开始循环，return false
23 } else {
24 return false;
25 }
26 }
27 return true;
28 }
29 };
1. 两数之和
因为要通过查找数组中的值来返回下表，所以需要同时存储两个不同的元素，使用unordered_map存储
1 class Solution {
2 public:
3 vector<int> twoSum(vector<int>& nums, int target) {
4 std::unordered_map <int, int> map;
5 for (int i = 0; i < nums.size(); i++){
6 //遍历当前元素，并在map中查找是否存在匹配的key
7 auto iter = map.find(target - nums[i]);
8 if (iter != map.end()){
9 return {iter->second, i};
10 }
11 //若不存在匹配的key,则将key和下表存入map
12 map.insert(pair<int, int>(nums[i], i));
13 }
14 return {};
15 }
16 };
标签：容器,set,map,int,随想录,202,键值,unordered,两数
From： https://www.cnblogs.com/zsqy/p/16736858.html