文章目录
1.哈希表理论基础
什么时候想到用哈希法：当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。
参考：代码随想录，哈希表理论基础：内容比较多，尤其是C++的一些哈希结构，比如set、map等等，还是比较多的，然后里面还有什么红黑树的内容，详细的去看里面的讲解吧。
2.242.有效的字母异位词
参考：代码随想录242有效的字母异位词
2.1.题目
2.2.解答
这个题目和自己昨天做的2.5数组——76最小覆盖子串的题目非常像，说白了其实就是统计s和t中出现的字符的个数，要让他们完全相等。所以回到使用哈希表的判断准则：要快速判断集合中是否存在某个元素（或者统计元素出现的次数）。
这里思路就是统计26个小写字母中，s所包含的字符出现的次数，然后再统计t所包含的字符的次数，他们两个需要完全相等。虽然统计的时候使用的是数组，但是前面基础知识讲解里说了，数组也是哈希表的一种形式。
注意：
- 注意这里为什么能够使用数组来做哈希表，因为数值范围已经给定了，就是26个字母的数值范围，所以可以使用数组（长度必须事先确定）来做哈希表。如果说数值范围没有实现给定，比如统计数字出现的次数，那么就不能用数组来做哈希表了。
- 另外，使用数组做哈希表的另一个可能的劣势是，如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。
class Solution
{
public:
bool isAnagram(string s, string t)
{
int record[26] = {0}; // 全部赋值为0
// 先统计s中字符出现的次数
for(auto& ss : s)
{
record[ss - 'a']++;
}
// 统计t中字符出现的次数，从s的统计结果中反向减小
for(auto& tt : t)
{
record[tt - 'a']--;
}
// 判断最后结果，如果s和t字符出现情况完全一样，则record应该都是0
for(auto& rr: record)
{
if(rr)
return false;
}
// 运行到这里说明record中全是0，则是异位单词
return true;
}
};
复杂度分析：时间复杂度为O(n)，空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为O(1)。
3.349. 两个数组的交集
3.1.题目
3.2.解答
注意：
- 这里只需要判断是否存在某个元素，而不需要统计元素出现的次数，因此使用
unordered_set即可，而不用使用unordered_map，因为只需要键，不需要值。 - 另外下面的代码中返回的结果一开始也是用
unordered_set存储，而不是直接用vector存储。这是因为nums2中可能有重复的元素，然后查找的时候如果用vector，那么在nums1中也存在的、nums2中的重复元素就会被重复放到vector中，导致结果中有重复元素。而题目要求是没有重复元素的，因此unordered_set正好满足没有重复元素的要求，当有重复元素的时候，insert函数就不会插入新的元素。
class Solution
{
public:
vector<int> intersection(vector<int> &nums1, vector<int> &nums2)
{
// 直接传入两个指针，构造unordered_set
unordered_set<int> nums1_set(nums1.begin(), nums1.end());
// 注意这里一定要用unorder_set，而不是vector，因为要求没有重复元素
unordered_set<int> result_set;
for(auto& num : nums2)
{
if(nums1_set.find(num) != nums1_set.end())
{
// 这里就体现了为什么result_set是unordered_set，而不是vector，因为结果需要去重
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};
4.202. 快乐数
参考：代码随想录202. 快乐数
4.1.题目
4.2.解答
注意乍一看这个问题和哈希表好像毫无关系，但是实际上解题的关键点在于题目中提示的可能是无线循环始终不到1。其实这个无线循环意思就是会重复出现之前的情况，比如之前循环过程中出现了123这个数，然后循环算了半天结果又变成了123，那么此时就陷入了循环中。可以发现，只要是循环过程中不出现之前出现过的结果，那么就不会陷入循环，那么最后一直循环就一定会有解（这里暂且从数学上认为是不包括无限非重复循环吧，比如圆周率那种无限循环）。
所以此时问题就转化成了每次计算的结果查看它是否出现过，如果出现过则会进入循环，那么它永远不会到1，因此返回false。如果没出现过，那么就继续求解过程，直到最后计算结果是1，返回true。
class Solution
{
public:
bool isHappy(int n)
{
unordered_set<int> record;
while(true)
{
int num = getNum(n); // 先计算平方和
if(num == 1)
return true;
if(record.find(num) != record.end())
return false;
record.insert(num);
n = num;
}
}
private:
// 给一个数n，计算它的各个位置上的数字的平方和
int getNum(int n)
{
int sum = 0;
while(n)
{
int num = n % 10; // 个位数
sum += num * num;
n /= 10; // 把各位除掉，取前面的位数
}
return sum;
}
};
5.1两数之和
参考：代码随想录1. 两数之和
5.1.题目
5.2.解答
这个题目还是比较有意思的，首先题目说了假设最后只有唯一的答案。但是同一个元素不能在答案中重复出现，比如示例3中给出的答案，输出是[0, 1]，而不是[0, 0]。
求解思路：在遍历数组的时候，只需要向map去查询是否有和目前遍历元素比配的数值，如果有，就找到的匹配对；如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。
注意：为什么要用map，而不能用set？因为最后我们要返回索引，所以要用map的键存访问过的值，而map的值访问对应的索引。set只包含键，无法存储值。
其次仔细分析这个思想的话，感觉和之前做的双指针删除数组中的指定元素差不多。这里也是先用一个“快指针”去遍历整个数组，然后“慢指针”指向的位置存储的是快指针所在元素。只不过我们为了快速查找，使用了map这种哈希表的形式。
class Solution
{
public:
vector<int> twoSum(vector<int> &nums, int target)
{
unordered_map<int, int> record;
for(int i = 0; i < nums.size(); i++)
{
int num = target - nums[i]; // 另一半数
auto res = record.find(num); // 在map中寻找是否有另一半数
// 如果找到了，则程序结束
if(res != record.end())
return {res->second, i};
// 运行到这里说明没找到，则把当前数值和索引存起来，给后面的数查找使用
record.insert(pair<int, int>(nums[i], i));
}
return {-1, -1};
}
};