常见的三种哈希数据结构：
数组
set-集合
map-映射
std::unordered_set-底层实现时哈希表
std::set 和std::multiset 的底层实现是红黑树，key值有序，key值不可修改，只能删除和增加
std::unordered_map 底层实现为哈希表，
std::map 和std::multimap 的底层实现是红黑树，key值有序，不可修改
使用集合来解决问题，优先使用unordered_set，因为它的查询和增删效率是最优，需要集合有序，使用set，有序且有重复元素，使用multiset
class Solution {
public:
bool isAnagram(string s, string t) {
int record[26] = {0};
int lens = s.length();
int lent = t.length();
for(int i=0;i<lens;i++)
{
record[s[i]-'a']++;
}
for(int j=0;j<lent;j++)
{
record[t[j]-'a']--;
}
for(int i=0;i<26;i++)
{
if(record[i]!=0)
return false;
}
return true;
}
};
● 242.有效的字母异位词
题目链接：
https://leetcode.cn/problems/valid-anagram/
算法思想：
求一个数组的元素是否在另一个数组中出现，且出现的次数相同。我们可以想到用哈希表法。
因为字符串中都是字母，可以定义一个26个元素的数组作为哈希表，数组下标映射到字符串中的值，数组的值为字符串出现的次数。
初始化哈希表arr[26]={0}, 将数组1存入到哈希表中arr。遍历数组2，如果出现在arr中，arr的数量-1。
最后遍历arr，如果arr中元素的值有非0的情况，返回false，否则true。
● 349. 两个数组的交集
题目链接：https://leetcode.cn/problems/intersection-of-two-arrays/
算法思想：
即求一个数组的元素是否在另一个元素中，我们可以想到用哈希表。
将第一个数组的元素存入一个哈希表中，遍历第二个数组，当数组2的元素出现在哈希表中，存入result集合中。
代码：
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result;
unordered_set<int> set1(nums1.begin(), nums1.end());
int len2=nums2.size();
for(int i=0;i<len2;i++)
{
if(set1.find(nums2[i])!=set1.end())
result.insert(nums2[i]);
}
return vector<int>(result.begin(), result.end());
}
};
● 202. 快乐数
题目链接：https://leetcode.cn/problems/happy-number/
思路：
关键在于如何判断是否无限循环。如果无限循环，平方和在之前必定会出现过，因此需要用一个哈希表来存之前出现的和。
此外，求一个数字的分子分母平方和是一个固定写法，灵活运用/和%。
class Solution {
public:
int get_sum(int n)
{
int sum=0;
while(n!=0)
{
int r = n%10;
n = n/10;
sum += r*r;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> result;
result.insert(n);
while(n!=1)
{
n = get_sum(n);
if(result.find(n)!=result.end())
return false;
result.insert(n);
}
return true;
}
};
● 1. 两数之和
题目链接：
https://leetcode.cn/problems/two-sum/
算法核心：在数组中寻找某个元素，可以想用到哈希来实现。因为需要获取到对应的位置，因此用unordered_map<int，into>实现。
算法思想：
首先把数据元素全部存入map中，
然后遍历数组元素，计算target-nums[i],即为我们要找的值，如果在map中找到，且下标不等于i，就返回。
代码：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> arr;
vector<int> result;
for(int i=0;i<nums.size();i++)
{
arr[nums[i]] = i;
}
for(int i=0;i<nums.size();i++)
{
int findnum = target-nums[i];
if(arr.find(findnum)!=arr.end())
{
int pos = arr[findnum];
if(pos!=i)
{
result.push_back(i);
result.push_back(pos);
break;
}
}
}
return result;
}
};
