常見的三種哈希數(shù)據(jù)結(jié)構(gòu)：
數(shù)組
set-集合
map-映射
std::unordered_set-底層實現(xiàn)時哈希表
std::set 和std::multiset 的底層實現(xiàn)是紅黑樹，key值有序拿撩，key值不可修改半沽，只能刪除和增加
std::unordered_map 底層實現(xiàn)為哈希表呢岗，
std::map 和std::multimap 的底層實現(xiàn)是紅黑樹唠叛，key值有序硫豆，不可修改
使用集合來解決問題饭冬，優(yōu)先使用unordered_set嘀韧，因為它的查詢和增刪效率是最優(yōu)，需要集合有序绝淡，使用set宙刘，有序且有重復(fù)元素，使用multiset
class Solution {
public:
bool isAnagram(string s, string t) {
int record[26] = {0};
int lens = s.length();
int lent = t.length();
for(int i=0;i<lens;i++)
{
record[s[i]-'a']++;
}
for(int j=0;j<lent;j++)
{
record[t[j]-'a']--;
}
for(int i=0;i<26;i++)
{
if(record[i]!=0)
return false;
}
return true;
}
};
● 242.有效的字母異位詞
題目鏈接：
https://leetcode.cn/problems/valid-anagram/
算法思想：
求一個數(shù)組的元素是否在另一個數(shù)組中出現(xiàn)够委，且出現(xiàn)的次數(shù)相同荐类。我們可以想到用哈希表法。
因為字符串中都是字母茁帽，可以定義一個26個元素的數(shù)組作為哈希表玉罐，數(shù)組下標(biāo)映射到字符串中的值，數(shù)組的值為字符串出現(xiàn)的次數(shù)潘拨。
初始化哈希表arr[26]={0}, 將數(shù)組1存入到哈希表中arr吊输。遍歷數(shù)組2，如果出現(xiàn)在arr中铁追，arr的數(shù)量-1季蚂。
最后遍歷arr，如果arr中元素的值有非0的情況，返回false扭屁，否則true算谈。
● 349. 兩個數(shù)組的交集
題目鏈接：https://leetcode.cn/problems/intersection-of-two-arrays/
算法思想：
即求一個數(shù)組的元素是否在另一個元素中，我們可以想到用哈希表料滥。
將第一個數(shù)組的元素存入一個哈希表中然眼，遍歷第二個數(shù)組，當(dāng)數(shù)組2的元素出現(xiàn)在哈希表中葵腹，存入result集合中高每。
代碼：
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result;
unordered_set<int> set1(nums1.begin(), nums1.end());
int len2=nums2.size();
for(int i=0;i<len2;i++)
{
if(set1.find(nums2[i])!=set1.end())
result.insert(nums2[i]);
}
return vector<int>(result.begin(), result.end());
}
};
● 202. 快樂數(shù)
題目鏈接：https://leetcode.cn/problems/happy-number/
思路：
關(guān)鍵在于如何判斷是否無限循環(huán)。如果無限循環(huán)践宴，平方和在之前必定會出現(xiàn)過鲸匿，因此需要用一個哈希表來存之前出現(xiàn)的和。
此外阻肩，求一個數(shù)字的分子分母平方和是一個固定寫法带欢，靈活運用/和%。
class Solution {
public:
int get_sum(int n)
{
int sum=0;
while(n!=0)
{
int r = n%10;
n = n/10;
sum += r*r;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> result;
result.insert(n);
while(n!=1)
{
n = get_sum(n);
if(result.find(n)!=result.end())
return false;
result.insert(n);
}
return true;
}
};
● 1. 兩數(shù)之和
題目鏈接：
https://leetcode.cn/problems/two-sum/
算法核心：在數(shù)組中尋找某個元素烤惊，可以想用到哈希來實現(xiàn)洪囤。因為需要獲取到對應(yīng)的位置，因此用unordered_map<int撕氧，into>實現(xiàn)。
算法思想：
首先把數(shù)據(jù)元素全部存入map中喇完，
然后遍歷數(shù)組元素伦泥，計算target-nums[i],即為我們要找的值，如果在map中找到锦溪，且下標(biāo)不等于i不脯，就返回。
代碼：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> arr;
vector<int> result;
for(int i=0;i<nums.size();i++)
{
arr[nums[i]] = i;
}
for(int i=0;i<nums.size();i++)
{
int findnum = target-nums[i];
if(arr.find(findnum)!=arr.end())
{
int pos = arr[findnum];
if(pos!=i)
{
result.push_back(i);
result.push_back(pos);
break;
}
}
}
return result;
}
};
