基础知识
常用代码
哈希表一共有3种哈希结构，分别是数组、set（集合）、map（映射）
数组
数组就是把不同的元素映射到不同的地址运用数组创建哈希表，应当遵循以下两个原则：
1.所映射的元素的数值种类不多（比如26个字母）
2.映射关系比较好表达（比如26个字母，就可以用该元素-'a'作为映射）
set（集合）作为哈希表
数组大小有限，如果题目没有限制数值大小，且数组空间交大，哈希值较少，会容易造成浪费，这个时候我们就可以考虑使用set。
C++一共给set提供了以下三种数据结构，可以按照表中的效率，如果要查找的话，很明显unordered_set的效率更高一点，set和multiset的元素是有序的，区别在于，multiset的元素可以重复：
以下是set创建插入删除查询遍历的语法，其他两类只需要把set替换成multiset/unordered_set：
#include <set> // 包含头文件
int main() {
// 创建一个std::set
std::set<int> mySet;
// 插入元素
mySet.insert(10);
mySet.insert(20);
mySet.insert(30);
// 查找元素
if (mySet.find(20) != mySet.end()) {
// 元素存在
}
// 删除元素
mySet.erase(10);
// 遍历元素
for (const auto& element : mySet) {
// 使用 element
}
return 0;
}
map（映射）作为哈希表
map不同于set，map的每个元素对应一个value和一个key，能很快查询到的值是key值，C++同样也给map提供了3种数据结构：
，当需要统计一个元素出现的次数时，可以考虑使用map，以下是map的语法规则
//创建
std::unordered_map <int,int> map;
// 遍历当前元素，并在map中寻找是否有匹配的key
auto iter = map.find(target - nums[i]);
if(iter != map.end()) {
return {iter->second, i};
}
// 如果没找到匹配对，就把访问过的元素和下标加入到map中
map.insert(pair<int, int>(nums[i], i));
刷题总结
数组
LeetCode242有效的字母异词位
思路：把26个字母映射到一个长度为26的数组中，并通过数组的值去判断出现频率，最后遍历return。
解题犯的错：第一次写吧数组的初始化写错了，真的是太久没有写代码手生了。
本题很符合哈希表数组的要求，26个字母正好可以通过-'a'对应26个连续的地址，元素不多，映射关系比较好找，具体代码如下：
class Solution {
public:
bool isAnagram(string s, string t) {
//int hash[26]=0; 错误的数组初始化
int hash[26]={0};
int i=0;
for(i=0;i<s.size();i++)
{
hash[s[i]-'a']++;
}
for(i=0;i<t.size();i++)
{
hash[t[i]-'a']--;
}
for(i=0;i<26;i++)
if(hash[i]!=0) return false;
return true;
}
};
LeetCode383赎金信
这道题我第一次解用了map，把元素作为key值，把出现的次数作为value，代码很简单，如下：
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<char,int> base;
for(char a:magazine)
base[a]++;
for(char b:ransomNote)
{
if(base.find(b)!=base.end()&&base[b]>0)
base[b]--;
else
return false;
}
return true;
}
};
但这一题明显和上一题很类似，用数组空间复杂度会更低一些，思路还是和上题一样，26个地址对应26个字母，数组的值表示出现的次数，以及用数组一定要记得初始化，代码如下：
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
//这里记得要初始化啊，我刚开始没有初始化一个测试样例就没通过
int hash[26]={0};
//这里分出一种情况判断可以省下一部分时间
if(ransomNote.size()>magazine.size())
return false;
for(char a:magazine)
hash[a-'a']++;
for(char b:ransomNote)
{
if(hash[b-'a']>0)
hash[b-'a']--;
else
return false;
}
return true;
}
};
set
LeetCode349两个数组的交集
这题的思路就是把nums1中出现过的元素，存放到一个哈希表中，可以是unordered_set，也可以是数组（因为数组元素大小是0<x<=1000），然后通过nums2的查询，把能在哈希表中查询到的元素放入一个unordered_set（不用去重）中，以下是源代码：
两个unordered_set:
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;
unordered_set<int> nums_set(nums1.begin(),nums1.end());
for(int num:nums2)
{
if(nums_set.find(num)!=nums_set.end())
result_set.insert(num);
}
return vector<int>(result_set.begin(),result_set.end());
}
};
一个数组一个unordered_set：
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
//哈希表数组做法
unordered_set<int> result_set;
//不要忘记初始化
int hash[1000]={0};
for(int i=0;i<nums1.size();i++)
{
hash[nums1[i]]=1;
}
for(int num:nums2)
{
if(hash[num]==1)
result_set.insert(num);
}
return vector<int>(result_set.begin(),result_set.end());
}
};
LeetCode202快乐数
思路：首先写一个summ函数，计算不同位数的平方和，本题的关键在于，如果不是快乐数，很有可能陷入无限循环中去，而这时候n可能会重复出现，我们正是利用这一点，创建一个unordered_set，每次计算完去查找有没有重复的数字，如果有重复的说明已经进入循环，直接return false。
所犯错误：因为本人比较菜，所以写的时候在一些地方卡住了：
1.while里面填什么，刚开始真的晕了好大一会儿，现在写总结文章的时候才觉得，既然可能是无限循环，通过return结束，直接写while（1）不就好了吗？
2.最好不要把函数名和变量名写得一样，我写得一样就报错了
3.最后！！！因为前面的代码太长，所以写到最后容易忘记最关键的一步，重新给n赋值！！！
代码如下：
class Solution {
public:
int summ(int n)
{
int sum=0;
while(n)
{
sum+=(n%10)*(n%10);
n=n/10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> result_set={0};
//某个憨憨在这里想了半天要while什么，返回去发现卡哥写了while（1）
while(1)
{
//我刚开始把函数名也名为sum，结果就报错了，这里函数名和变量名应该不能相同
int sum=summ(n);
if(sum==1)
return true;
else if(sum!=1)
{
if(result_set.find(sum)!=result_set.end())
return false;
else
result_set.insert(sum);
//第一次写忘记加了
n=sum;
}
}
}
};
map
LeetCode1两数之和
思路：用一层for循环去遍历数组，边遍历边把元素存入到 unordered_map数据类型中，以元素值为key，数组中的下标为value（因为题目要求返回下标），然后去查找map中有没有值为target-nums[i]的值，如果有就返回二者下标，没有就把这个元素存入并继续遍历，具体代码如下：
class Solution {
public:
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 {};
}
};
LeetCode454四数相加II
四个数组前两个创建一个unordered_map，用key值记录两数相加之和，用value值记录这个和出现的次数，剩下的思路和上题类似，遍历剩下的两个数组，寻找有没有int target=-(c+d)，并把符合条件的key值加给count，具体代码如下：
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int> map;
int count=0;
for(int a:nums1)
{
for(int b:nums2)
{
map[a+b]++;
}
}
for(int c:nums3)
{
for(int d:nums4)
{
int target=-(c+d);
if(map.find(target)!=map.end())
{
count+=map[target];
}
}
}
return count;
}
};
双指针法
总所周知，哈希表章节可以不用哈希表（狗头），以下两题思路类似，只是多了一层for循环，因此展开细讲其中一道：
LeetCode15两数之和
LeetCode18四数之和
看到这道题，本能还是和两数之和一样，想使用哈希法，但是三个数字要去重，实行起来会很麻烦，所以后来听了卡哥的双指针法感觉让人眼前一亮。
思路：首先对数组进行升序排序，然后让i从第一个遍历到最后一个，设置左右两个指针，分别指向i的后一个和最后一个元素，如果nums[i] (本层循环的最小值)大于0，那么后面的就不用进行。
用一个while循环来改变左右两个指针，最终返回
尽管如此，本题的难点依旧在去重操作上，首先是对i的去重，我们判断nums[i]和nums[i-1]是否相等，如果相等的话，这重循环就不用进行了，用continue跳过；
其次是对left和right的去重，要放到while循环的末尾位置，确保如果符合条件的话，有一组数据已经写入result数组中，本题的源代码如下：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size();i++)
{
int left=i+1;
int right=nums.size()-1;
if(nums[i]>0)
return result;
if(i>0&&nums[i]==nums[i-1]) continue;
while(left<right)
{
if(nums[i]+nums[left]+nums[right]<0)
left++;
//我的天呐，这里第一次少打了一个else就错了，选择语句没有那么简单
else if(nums[i]+nums[left]+nums[right]>0)
right--;
else
{
result.push_back(vector<int>{nums[i],nums[left],nums[right]});
left++;
right--;
//这里我一开始用的是if，但是有很多测试用例通过不了，后来改成while报错，再后来加上了left<right才正确
while(nums[left]==nums[left-1]&&left<right) left++;
while(nums[right]==nums[right+1]&&left<right) right--;
}
}
}
return result;
}
};
我这里把while和if用错了，这里要注意应该是while而不是if，因为重复值可能不止一个。
总结
1.这两天时间比较赶，后面可以认真看一下哈希表的有关知识，了解一下哈希表的原理。
2.要坚持呀要坚持呀！加油！