哈希表理论基础
- 用法：一般哈希表都是用来快速判断一个元素是否出现集合里，哈希法牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找
eg:例如要查询一个名字是否在这所学校里，要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1)就可以做到 - 哈希碰撞的两种冲突解决方法
- 拉链法：链表
- 线性探测法：向后顺延(哈希表的tablesize > datasize)
- 三种哈希结构
- 数组
- set 集合
- map 映射
242有效的字母异位词（哈希——数组）
根据字母直接映射到相应位置
bool isAnagram(string s, string t) {
if(s.length()!=t.length())
return false;
vector<int> v(26,0);
for(int i=0;i<s.length();i++){
v[s[i]-'a']++;
v[t[i]-'a']--;
}
for(int j=0;j<26;j++)
if(v[j]!=0)
return false;
return true;
}
349两个数组的交集（哈希-set）
nums={0,1,1000000}，若用数组，则需要开规模为1000001的空间，造成极大浪费
unordered_set的用法
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 i = 0; i < nums2.size(); i++) {
if (nums_set.find(nums2[i]) != nums_set.end())
result_set.insert(nums2[i]);
}
return vector<int>(result_set.begin(), result_set.end());
}
202快乐数（哈希-set）
int getSum(int n) {
int sum = 0;
while (n)
{
sum += (n % 10) * (n % 10);
n = n / 10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> set;
int sum = n;
while (1)
{
sum = getSum(sum);
if (sum == 1)
return true;
if (set.find(sum) != set.end())
return false;
else
set.insert(sum);
}
}
1两数之和（哈希-map(key，value)）
查找一个元素target-x(key)是否出现过，并且找出它的下标(value)
vector<int> twoSum(vector<int>& nums, int target) {
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 {};
}