本文最后更新于 72 天前，其中的信息可能已经有所发展或是发生改变。
前置知识
在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：
| 集合 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
|---|---|---|---|---|---|---|
| std::set | 红黑树 | 有序 | 否 | 否 | O(log n) | O(log n) |
| std::multiset | 红黑树 | 有序 | 是 | 否 | O(logn) | O(logn) |
| std::unordered_set | 哈希表 | 无序 | 否 | 否 | O(1) | O(1) |
std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。
| 映射 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
|---|---|---|---|---|---|---|
| std::map | 红黑树 | key有序 | key不可重复 | key不可修改 | O(logn) | O(logn) |
| std::multimap | 红黑树 | key有序 | key可重复 | key不可修改 | O(log n) | O(log n) |
| std::unordered_map | 哈希表 | key无序 | key不可重复 | key不可修改 | O(1) | O(1) |
std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。
当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。
242.有效字母的异位词
利用数组实现的哈希表即可.
class Solution
{
public:
bool isAnagram(string s, string t)
{
int record[26] = {0};
for (int i = 0; i < s.size(); i++)
{
record[s[i] - 'a']++;
}
for (int i = 0; i < t.size(); i++)
{
record[t[i] - 'a']--;
}
for (int i = 0; i < 26; i++)
{
if (record[i] != 0)
{
return false;
}
}
return true;
}
};
349.两个数组的交集
主要是STL不熟悉
class Solution
{
public:
vector<int> intersection(vector<int> &nums1, vector<int> &nums2)
{
unordered_set<int> result;
unordered_set<int> nums_set(nums1.begin(), nums1.end());
for (int num : nums2)
{
if (nums_set.find(num) != nums_set.end()) // 如果find方法返回的迭代器不等于集合的结束迭代器（即找到了num），则条件表达式nums_set.find(num) != nums_set.end()为true。
{
result.insert(num);
}
}
return vector<int>(result.begin(), result.end());
}
};
202.快乐数
class Solution
{
public:
bool isHappy(int n)
{
unordered_set<int> checkSet;
int sum = 0;
while (checkSet.find(sum) == checkSet.end())//注意这里
{
checkSet.insert(sum);
sum = 0;//不要忘了重置sum
while (n)
{
sum = sum + (n % 10) * (n % 10);
n /= 10;
}
if (sum == 1)
{
return true;
}
else
{
n = sum;
}
}
return false;
}
};
1.两数之和
class Solution
{
public:
vector<int> twoSum(vector<int> &nums, int target)
{
std::unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++)
{
// 遍历当前元素，并在map中寻找是否有匹配的key
auto iter = map.find(target - nums[i]);
if (iter != map.end())
{
return {iter->second, i};
}
// 如果没找到匹配对，就把访问过的元素和下标加入到map中
map.insert(pair<int, int>(nums[i], i));
}
return {};
}
};
菜