常見的三種哈希數(shù)據(jù)結(jié)構(gòu)：
數(shù)組
set-集合
map-映射
std::unordered_set-底層實(shí)現(xiàn)時哈希表
std::set 和std::multiset 的底層實(shí)現(xiàn)是紅黑樹，key值有序，key值不可修改，只能刪除和增加
std::unordered_map 底層實(shí)現(xiàn)為哈希表，
std::map 和std::multimap 的底層實(shí)現(xiàn)是紅黑樹，key值有序，不可修改
使用集合來解決問題，優(yōu)先使用unordered_set，因?yàn)樗牟樵兒驮鰟h效率是最優(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ù)相同。我們可以想到用哈希表法。
因?yàn)樽址卸际亲帜福梢远x一個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ù)字的分子分母平方和是一個固定寫法，靈活運(yùn)用/和%。
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ù)組中尋找某個元素，可以想用到哈希來實(shí)現(xiàn)。因?yàn)樾枰@取到對應(yīng)的位置，因此用unordered_map<int，into>實(shí)現(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;
}
};
