leetcode哈希表(哈希映射和哈希集合)题型大总结！全面重点的哈希函数介绍！
哈希表分为哈希集合和哈希映射。
重点知识：
哈希映射是键值对(key,value)的映射。
定义哈希映射：Unordered_map<type,type> hash_name
找哈希表中的特定键：auto it=hash_name.find(特定键) 这个函数返回的it是一个迭代器，it->first返回特定键，it->second返回特定键对应的值。
遍历哈希表：for(auto it=hash_name.begin();it!=hash_name.end();it++) {cout<<(*it)<<endl}
给哈希表赋新的键值对：Hash_name[键]=键对应的值
改变键所指的值：Hash_name[键]=键对应的值；Hash_name[键]++
哈希集合是存储非重复值的集合
定义哈希集合：unordered_set<type> hash_name
判断哈希集合中是否有某个值：hash_name.count(该值)，如果有该值小于等于0，就不存在
给哈希集合插入新值：hash_name.insert(该值)
清除哈希集合中的值：hash_name.erase(该值)
求哈希集合的大小：hash_name.size()
C++ 的哈希表里面的元素没有固定顺序，因此借助一个 vector 按序存储哈希表 dic 中的 key ，第二轮遍历此 vector 即可。
题1：（哈希映射）
答案：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> myhash;
for (int i = 0; i < nums.size();i++) {
auto it = myhash.find(target - nums[i]);
if (it != myhash.end())
return{ it->second,i };
myhash[nums[i]] = i;
}
return{};
}
};
第一步：发现myhash中没有等于9-2=7的键，然后将键2填进哈希表
| 2 |
|
|
|
| 0 |
|
|
|
第二步：发现myhash中有等于9-7=2的键，返回键2对应的值0
整个哈希表应该是：
| 2 |
7 |
11 |
15 |
| 0 |
1 |
2 |
3 |
题2：（哈希集合）
注意这个题也包含滑动窗口的知识
答案：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> myset;
int right = 0;
int ans = 0;
for (int left = 0; left < s.size(); left++) {
while (right < s.size() && !myset.count(s[right])) {
myset.insert(s[right]);
right++;
}
if (myset.size() > ans) ans = myset.size();
myset.erase(s[left]);
}
return ans;
}
};
题3：（哈希集合）
、
答案：
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
unordered_set<int> myhash;
for (int i = 0; i < nums.size(); i++) {
if (!myhash.count(nums[i]))
myhash.insert(nums[i]);
else
return nums[i];
}
return NULL;
}
};
题4：（哈希表）
答案：
方法一：先遍历数组用哈希表统计元素及其出现次数，再遍历数组对照哈希表得到第一个不重复的数
class Solution {
public:
char firstUniqChar(string s) {
if (s == "") return ' ';
unordered_map<char,int> myhash;
for (int i = 0; i < s.size(); i++) {
if (!myhash.count(s[i]))
myhash[s[i]]=1;
else
myhash[s[i]]++;
}
for (int j = 0; j < s.size(); j++) {
auto it = myhash.find(s[j]);
if (it->second == 1)
return s[j];
}
return ' ';
}
};方法二：有序哈希表，只遍历一遍数组,再遍历一遍vector。这个vector比原数组要短。因为对于后面重复的元素它不储存，只有所有元素第一遍出现时才储存。所以效率更高。
class Solution {
public:
char firstUniqChar(string s) {
if (s == "") return ' ';
vector<char> res;
unordered_map<char, int> myhash;
for (int i = 0; i < s.size(); i++) {
if (!myhash.count(s[i]))
{
myhash[s[i]] = 1;
res.push_back(s[i]);
}
else
myhash[s[i]]++;
}
for (int j = 0; j < res.size(); j++) {
auto it = myhash.find(res[j]);
if (it->second == 1)
return res[j];
}
return ' ';
}
};