算法 ---哈希表

一、哈希介绍

是什么

存储数据的容器

什么用

快速查找某个元素

什么时候用哈希表

频繁的查找某一个数的时候

怎么用哈希表

（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<string> 然后遍历strs，将他的值排序后如果hash表中含有，插入到vector<string>中

（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;}};