哈喽哈喽，周末过得咋样啊~今天我们带来的是哈希表，哈希就是通过一些方法将数据映射到一个容器的数据结构，一般会有三个容器：数组，map和set，怎么使用呢，让我们来看一下
题目引用
- 有效的字母异位词
- 两个数组的交集
- 快乐数
- 两数之和
1.有效的字母异位词
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
我们来分析一下题目
首先我们先想一下暴力做法，做一个嵌套循环，然后每一个都在另外一个字符串里面进行比对，并给一个bool类型数组用来标记是否被遍历过。但是太过麻烦了，时间复杂度会到达O(N^2)。那么为了减少时间复杂度，我们可以借助哈希这个思想来解决问题。
首先我们初始化一个长度为26的数组，数值都为0，通过nums[i]-‘a’来映射到数组中，总共映射两次，第一次将字符串1遍历一遍，将其每一位映射到数组中，第二次遍历字符串2，将其每一位映射到数组中减去该位置的数，最后判断这个数组里面是否有!=0的数，如果有，那么说明字符串2里面有字符串1没有的字母，或者是字母数量不匹配，返回false。
那么我们直接看代码:
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;}
通过几次遍历将其优化到O(N)的时间复杂度，且还有优化的空间，我们可以将最后的检查放到第二次遍历字符串2中，省略一次遍历，那么这个方法就交给屏幕前的你来实现啦~
2.两个数组的交集
给定两个数组 nums1 和 nums2 ，返回 它们的
交集
。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
首先我们还是想一下暴力做法，首先对数组进行排序，排完之后去重，去重之后嵌套循环寻找交集。显得非常繁琐且麻烦。
这里我们呢就可以引进set来解决问题了，那么set呢又有三种
set
multiset
unordered_set
前两种是底层都是用红黑树实现的，第三种是通过哈希表实现的前两种实现了排序，最后一种没有。且这三种都实现了去重，所以我们就可以放心食用啦~这里多提一嘴，STL对于C++和算法都是不可或缺的一部分，有缺漏一定要去复习。
我们通过unordered_set实现了一个结果哈希表res_set，一个公用哈希表nums_set，将nums1的数组放入nums_set中，再遍历nums2数组，使用find函数进行查找，如果不为空就插入res_set中。最后返回res_set。
来看代码：
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> res_set;unordered_set<int> nums_set(nums1.begin(),nums1.end());for(auto num:nums2){if(nums_set.find(num)!=nums_set.end()){res_set.insert(num);}}//这里将set转成vectorreturn vector<int>(res_set.begin(),nums_set.end());}
3.快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：
输入：n = 2
输出：false
我们来看一下题目，要求我们判断一个数的每一位的平方相加为1，那么就是快乐数，如果进入无限循环那么就不是快乐数。
所以我们这里利用unordered_set初始化一个哈希表，用来记录每次数字变化后的结果。直到数字变为1返回true或者在set中再次找到这个数说明进入了无限循环，返回false。
来看代码
int getHappy(int n){int ret=0;while(n){int tmp=n%10;ret+=tmp*tmp;n/=10;}return ret;}bool isHappy(int n) {unordered_set<int> res_set;while(1){int num=getHappy(n);if(num==1){return true;}if(res_set.find(num)!=res_set.end()){//找到相同的数了return false;}else{res_set.insert(num);}n=num;}}
4.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
先想一个暴力做法，嵌套循环这个数组，找到相加为target的就返回下标，循环结束找不到就返回-1，-1。
那么这道题怎么用哈希思想解决呢？
这里我们就要请出map
map分为
map
multimap
unordered_map
前两个是红黑树实现的，后一个是哈希表实现的，同样这道题不要求排序，用unordered_map就可以。map的key为数组下标对应的值，value为下标i。遍历一遍数组，用迭代器iter接受find(target-nums[i])的值，如果找到了，直接返回下标，找不到就插入map。
vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> map;for(int i=0;i<nums.size();i++){auto iter=map.find(target-nums[i]);if(iter!=map.end()){return {i,iter->second};}else{map.insert(pair<int,int>(nums[i],i));}}return {-1,-1};}
总结
哈希这种思想对于需要在集合中查找和修改的题目来说比较方便，我们也应该好好掌握~
