3 哈希表
# 哈希表
## 1 哈希表理论基础
### 1.1 什么是哈希表
> 哈希表(hash table):根据关键码的值而直接进行访问的数据结构。
- hash表解决问题：快速判断一个元素是否出现集合里
- hash函数：哈希函数如下图所示，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值
此时如果如果hashCode得到的数值大于哈希表的大小，也就是大于tableSize，保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做取模的操作，但是如果数量本身就大于哈希表的大小，则会出现哈希碰撞
- hash碰撞：
一般哈希碰撞有两种解决方法， 拉链法和线性探测法。
- 拉链法
在碰撞的位置的元素都存储在链表中，这样就可以通过索引找到相关的元素。
拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。
- 线性探测法
使用线性探测法，一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。冲撞的位置直接向下寻找空位安放。
- 常见的哈希结构
- 数组
- 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。
# 2 有效的字母异位词
## 题目
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入: s = "anagram", t = "nagaram" 输出: true
示例 2: 输入: s = "rat", t = "car" 输出: false
说明: 你可以假设字符串只包含小写字母。
## 思路
定义数组作为哈希表，因为字母只有26个，一一对应的代价很小，哈希映射函数为ascii码的顺序对应字母顺序，两个循环在s字符串循环对应+1，t字符串循环对应-1，最终数组全为0就是false，否则true
## 代码
```C++
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;
}
```
# 3 两个数组的交集
## 题目
题意：给定两个数组，编写一个函数来计算它们的交集。
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
说明： 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序
## 思路
std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表， 使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。
## 代码
```C++
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;
unordered_set<int> nums1_set(nums1.begin(),nums1.end());
for(int num:nums2){
if(nums1_set.find(num)!=nums1_set.end()){
result_set.insert(num);
}
}
return vector<int>(result_set.begin(),result_set.end());
}
```
# 4 快乐数
## 题目
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。
示例：
输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
## 思路
判断是否循环，循环就不是快乐数，当看到是否有重复时就想到哈希法，终止条件：重复或者和为1
## 代码
```C++
bool isHappy(int n) {
unordered_set<int>happySet;
int happyNum = 0;
while(happyNum != 1){
if(happySet.find(n)!=happySet.end()) return false;
happySet.insert(happyNum);
happyNum = 0; //重置以重新计算
while(n != 0){
happyNum += (n % 10) * (n % 10);
n /= 10;
}
n = happyNum;
}
return true;
}
```
# 5 两数之和
## 题目
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
## 思路
我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。
## 代码
```C++
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 {iter->second,i};
map.insert(pair<int,int>(nums[i],i));
}
return {};
}
```
注意map的使用方式
# 6 四数相加II
## 题目
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。
## 思路
map，key为两数之和，value为出现的次数，统计出现次数即可
## 代码
```C++
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int> map;
for(int num1 : nums1){
for(int num2 :nums2){
map[num1 + num2]++;
}
}
int count = 0;
for(int num3 : nums3){
for(int num4 :nums4){
if(map.find(-(num3 + num4)) != map.end()) count+=map[-(num3 + num4)];
}
}
return count;
}
```
# 7 赎金信
## 题目
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
## 思路
跟有效字母异味词相似，但是这里只需要管ransomnote在magazine中够出现就行。int一个record[26]数组存储字母个数。
## 代码
```C++
int record[26]={0};
for(int i =0;i<magazine.size();i++){
record[magazine[i]-'a']++;
}
for(int i = 0;i < ransomNote.size() ; i++){
record[ransomNote[i]-'a']--;
}
for(int i = 0 ;i<26;i++){
if(record[i]<0) return false;
}
return true;
```
# 8 三数之和
## 题目
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
## 思路
可以使用哈希法，但是操作比较困难，两个for循环，主要要去重需要很多判断。这里可以使用双指针法，更加高效
## 代码
```C++
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(),nums.end());
for(int i = 0 ; i < nums.size() - 2 ; i++){
if(nums[i] > 0) return result;
if(i>0 && nums[i] == nums[i - 1]) continue;
int right = nums.size() - 1;
int left = i + 1;
while(left < right){
if(nums[i] + nums[left] + nums[right] > 0) right--;
else if(nums[i] + nums[left] + nums[right] < 0) left++;
else{
result.push_back({nums[i],nums[left],nums[right]});
while(right>left && nums[right] == nums [right - 1]) right--;
while(right>left && nums[left] == nums [left + 1]) left--;
left++;
right--;
}
}
}
return result;
}
```
其中的去重操作细节，在排序之后，相邻的相同数字跳过，但又需要考虑(-1,-1,2)这种情况，所以`if(i>0 && nums[i] == nums[i - 1]) continue;`
# 9 四数之和
## 题目
题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
## 思路
同样双指针，多一层for循环
## 代码
```C++
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(),nums.end());
for(int i = 0;i < nums.size() - 3 ; i++){
if(nums.size() < 4) return result;
for(int j = 1;j < nums.size() - 2 ; j++){
if(i >= j || (i >= 1 && nums[i] == nums[i-1]) ) continue;
if(j > i + 1 && nums[j] == nums[j-1]) continue;
int right = nums.size() - 1;
int left = j + 1;
while(left < right){
if((long)nums[i]+nums[j]+nums[right]+nums[left]>target) {
right--;
}
else if((long)nums[i]+nums[j]+nums[right]+nums[left]<target){
left++;
}
else{
result.push_back({nums[i],nums[j],nums[left],nums[right]});
while(right>left&&(nums[right]==nums[right-1])){
right--;
}
while(right>left&&(nums[left]==nums[left+1])){
left++;
}
left++;
right--;
}
}
}
}
return result;
}
```
- 注意点1：可能越界，超过int指针最大值
- 注意点2：保证i < j，并且对于i和j都要剪枝