哈希表基础：代码随想录
总结：哈希表是拿空间换时间，当需要快速知道一个元素是否在某一集合中时，可以使用。
常见的三种哈希结构：（摘自代码随想录）
数组
set （集合）
map(映射)
std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。
std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。
当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。
那么再来看一下map ，在map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。
题目：242.有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
思路：最简单的哈希表使用方式，只需要将s 中的所有字母放入哈希表中，之后便利 t 中的字母并每次检查字母是否在哈希表中，并哈希表中对应字母的值减一。若t 中的字母都能在哈希表中找到，并且在遍历完成后哈希表的值为0，表明为 字母异位词。
class Solution {
public:
bool isAnagram(string s, string t) {
int record[26] = {0};
for(int i = 0;i < s.size();i++)
{
int index = s[i] -'a';
record[index] ++ ;
}
for(int i = 0; i< t.size();i++)
{
int index = t[i] -'a';
record[index] -- ;
}
for(int i = 0; i<26;i++)
{
if(record[i] != 0){
return false;
}
}
return true;
}
};小技巧：可以利用ascii来实现，例如t[i] -'a'就是t[i]到'a'的距离为一个正整数，因此可以直接用一个数组来作为哈希表。
题目：349. 两个数组的交集
给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
思路：开始的思路和上一题的思路相同，想用一个数组将所有的数值纳入其中，但是该题写出0 <= nums1[i], nums2[i] <= 1000，这说明里面的数字很大，这样数组就需要很大，相对来说set会更加的方便，且set的唯一性（Uniqueness）也便于这道题目结果的输出。（应为cpp的特性还在摸索，自己手巧了一遍代码随想录中的代码）
注意：数组的速度是比set快的，若是能用数组还是使用数组
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()){
result.insert(num);
}
}
return vector<int>(result.begin(),result.end());
}
};题目：202. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
思路：主要需要处理的是怎么判断是否陷入无限循环 ，此时可以使用set，将每次的计算结果放入set中，在整个计算过程中若出现计算的结果存在于set中则说明循环了。
class Solution {
public:
int getsum(int num){
int sum = 0;
while(num != 0){
sum += (num%10) * (num%10);
num /= 10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> record;
while(1){
n = getsum(n);
if(n == 1){
return true;
}
if(record.find(n) != record.end()){
return false;
}
record.insert(n);
}
}
};题目：1.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
思路：第一次做的时候用的暴力破解，两层for循环😂。实际上这题可以使用map来做，只需要使用一次for循环即可。将target-num[i]即为我们需要寻找的数字，因此只需要将这个值在哈希表中寻找即可。
为什么不用set？因为需要保存数组中元素的值和索引值，因此需要使用map
注意：需要将所有操作在一次循环中完成，不要先将所有值放入map后再查找，会导致重复的问题。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> nums_map;
for(int i = 0; i< nums.size();i++){
auto iter = nums_map.find(target - nums[i]);
if(iter != nums_map.end()){
return {iter->second,i}; //因为存放在nums_map中的值的索引一定是先于i的因此这么返回
}
nums_map.insert(pair<int,int>(nums[i],i));
}
return {};
}
};
评论