哈希表理论基础
当需要判断一个元素是否在一个集合中，哈希表的时间复杂度只有O(1)。
哈希表有一个映射的操作，当映射的元素在同一个索引下标的位置，就会引发哈希碰撞。
哈希碰撞的两种解决方法：拉链法
线性探测法
同时，哈希表还有常见的三种数据结构：分别是数组、集合set、映射map。
有效的字母异位词
这道题目有效考察了数组在哈希表中的应用
这道题的思路是定义一个数组，用来记录字符串t和s在数组中字符出现的次数。比如说字符串s中有a出现，数组0号位置就加一，数组t中有a出现，数组0号位置就减一，这样一来到最后，如果数组中所有的元素都是0，就可以知道这两个字符串是异位词。
class Solution {
public:
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;
}
};关于这里面record[s[i]-'a']++，比如说这里的s是rat，当i等于0时候，那么也就是record['r'-'a']++,'r'-'a'的相对位置就可以换成r在数组是第几个元素，这样'a'-’a'相对位置就是0，‘b'-’a'相对位置就是1，以此类推。
两个数组的交集
这道题主要是哈希表的set结构来处理问题的，因为返回的结构中是无序并且是单一的，因此我们可以选取unordered_set这种数据结构，我们设置一个result_set用来存放结果，然后将num1变成一个哈希表，我们将nums2中的数组进行比对，也就是看看nums2中的数据有没有在nums1中这个哈希表中有没有出现过，如果有的话，就将结果更新到result_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());
}
};其中for（int num ：num2)是C++11标准的写法，后面的话这些知识需要补上。
快乐数
这道题说到底就是一道哈希表的应用
主要思想是看那个无限循环，n的每个位置上的平方和都是一次sum，然后再次将sum变成n继续获得每个位置上的平方和，把每次获得的sum放在一个容器中，如果容器中有这个数了，那么就说明进入了无限循环，发现为1的话就说明结果走出了。
class Solution {
public:
int getSum(int n)//先获得n各个位上的平方和
{
int sum = 0;
while(n)
{
sum += (n%10)*(n%10);
n /= 10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> set;
while(1)
{
int sum = getSum(n);
if(sum == 1)
{
return true;
}
if(set.find(sum) != set.end())
{
return false;
}else{
set.insert(sum);
}
n = sum;
}
}
};两数之和
文章来源：https://www.toymoban.com/news/detail-456930.html
这道题需要我们的思维是先拿到一个元素，然后在数组中找另外一个元素和它相加等于目标值，依此遍历数组，哈希表的思想就是查询一个元素是否出现过，这道题可以使用哈希表的map来解题。因为我们需要存放元素的值还需要存放元素的下标，因此使用哈希表是最好的方法。文章来源地址https://www.toymoban.com/news/detail-456930.html
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
std::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};
}
else
{
map.insert(pair<int,int> (nums[i],i));
}
}
return {};
}
};到了这里，关于代码随想录day6｜哈希表理论基础、有效的字母异位词、两个数组的交集、快乐数、两数之和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
