算法-哈希表
目录
算法 —哈希表
一、哈希介绍
是什么
存储数据的容器
什么用
快速查找某个元素
什么时候用哈希表
频繁的查找某一个数的时候
怎么用哈希表
（1）容器（哈希表）
（2）用数组模拟哈希表（字符串的字符，数据范围很小的时候）
二、题目
1、两数之和
（1）题目
（2）解题思路
解题思路一：双指针，遍历整个数组，把符合条件的返回
解题思路二：用哈希表，将数组下标和值存起来，在遍历数组的时候，在哈希表中寻找目标值和当前遍历的值的差值
（3）代码实现
解法一：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
for(int i = 0; i<nums.size(); i++)
{
for(int j = i+1; j<nums.size(); j++)
{
if(nums[i]+nums[j]==target)
{
return{i,j};
}
}
}
return {-1,-1};
}
};
class Solution
{
public:
vector<int> twoSum(vector<int>& nums, int target)
{
for(int i = 0; i<nums.size();i++)
{
for(int j = 0; j<i;j++)
{
if(nums[i]+nums[j] == target)
{
return {i,j};
}
}
}
return {-1,-1};
}
};解法二：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
unordered_map<int,int> hash;
for(int i = 0 ; i<nums.size();i++)
{
int t = target - nums[i] ;
if(hash.count(t))
{
return {hash[t], i};
}
hash[nums[i]] = i;
}
return {-1,-1};
}
};2、判断数组是否重排
（1）题目
（2）解题思路
我们可以用数组模拟哈希表，开一个数为26的数组，首先遍历其中一个字符串将每一个字母-‘0’的位置–，然后再遍历另外一个字符串将每一个字母的-‘0’的字母++，最后遍历数组如果存在不是0的数就不是重排
（3）代码书写
class Solution
{
public:
bool CheckPermutation(string s1, string s2)
{
if(s1.size()!=s2.size())
{
return false;
}
int nums[26]={0};
for(int i = 0; i < s1.size(); i++)
{
nums[s1[i]-'a']++;
nums[s2[i]-'a']--;
}
for(int j = 0; j<26;j++)
{
if(nums[j]!=0)
return false;
}
return true;
}
};3、存在重复元素
（1）题目
（2）解题思路
我们创立一个哈希表，遍历nums，如果存在数组中的值则返回true，不存在数组中的则插入
（3）代码实现
class Solution
{
public:
bool containsDuplicate(vector<int>& nums)
{
unordered_set<int> hash;
for(auto x: nums)
if(hash.count(x))
return true;
else hash.insert(x);
return false;
}
};4、存在重复元素二
（1）题目
（2）解题思路
创建一个哈希表，遍历nums如果哈希表中存在该下标的值，判断该下标和原先所存储的小表达差值是否小于k，如果是，返回true，否则覆盖下标，如果哈希表中部存在该下标的值，则插入
（3）代码实现
class Solution
{
public:
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
unordered_map<int , int> hash;
for(int i = 0 ; i<nums.size(); i++)
{
if(hash.count(nums[i]))
{
if(i - hash[nums[i]]<=k)
{
return true;
}
else
{
hash[nums[i]] = i;
}
}
else
{
hash[nums[i]] = i;
}
}
return false;
}
};5、字母异位词分组
（1）题目
（2）解题思路
我们可以创立一个哈希表string ，vector
（3）代码实现
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs)
{
unordered_map<string ,vector<string>> hash;
for(auto&e: strs)
{
string tmp = e;
sort(tmp.begin(),tmp.end());
hash[tmp].push_back(e);
}
vector<vector<string>> ret;
for(auto &[x,y] : hash)
{
ret.push_back(y);
}
return ret;
}
};