©2020-2024 ioDraw All rights reserved
哈希表
1.哈希集
哈希集是一种功能简单的哈希结构。 哈希集的特点：只记录值（value）。
由于哈希集不能记录特殊的键值，因此我们无法将哈希集用于记录人物的段位了，我们只能记录人物是否存在于名单上。
1.1 建立哈希集
unordered_set<Type> hashset;
type:哈希集中变量类型，可以是int,string等；
hashset:哈希集地名称，任意取。
1.2 插入键
hashset.insert(3); //3 hashset.insert(4); //4
比如我们将3和4插入集合中
1.3 删除键
hashset.erase(3);
比如我们将3从哈希集合删除
1.4搜索键
哈希集的核心功能上线了——搜索。搜索某个键是否存在于哈希集内。
hashset.count();
如果存在返回1；
哈希集的主要功能就是，验证一个键是否已经在该哈希集中注册过。
1.5遍历哈希集
for (auto it = hashset.begin(); it != hashset.end(); ++it) { cout << (*it)
<< " "; }
2.哈希映射
哈希映射建立的是一种关系，所以哈希映射里同时拥有键和键值。
2.1 建立哈希映射
unordered_map<Type, Type> hashmap;
第一个Type是键的变量类型，第二个Type是键值的变量类型，hashmap是该哈希映射的名称。
2.2 插入键值对
hashmap[5] = 3; //5——3 hashmap[6] = 2; //6——2 hashmap[7] = 1; //7——1
2.3 删除键值对
hashmap.erase(5);
2.4 搜索键值对
hashmap.count(); //count函数返回值只能是1（存在）或0（不存在）。 hashmap.fine();
//使用find，返回的是被查找元素的位置，没有则返回map.end(）
2.5 遍历哈希映射
for (auto it = hashmap.begin(); it != hashmap.end(); ++it) { cout << "(" <<
it->first << "," << it->second << ") "; }
2.例题分析
2.1 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
#include<iostream> #include<vector> #include<unordered_map> using namespace
std; class Solution { public: static vector<int> twoSum(vector<int>& nums, int
target) { unordered_map<int, int> hashmap; for (int i = 0; i < nums.size();
++i) { auto it = hashmap.find(target - nums[i]); if (it != hashmap.end()) {
return { it->second,i }; } hashmap[nums[i]] = i; } return {}; } }; int main() {
vector<int> nums = { 2,7,11,15 }; int target = 9; vector<int> return_value=
Solution::twoSum(nums, target); for (auto i = return_value.begin(); i !=
return_value.end(); i++) { std::cout << *i << ' '; //利用迭代器输出vector的所有值。 } }
2.2 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
#include<iostream> #include<vector> #include<unordered_set> using namespace
std; class Solution { public: static int lengthOfLongestSubstring(string s) {
unordered_set<char> hashset; int ans = 0; // int left=0; //左指针 int right =
-1;//右指针 for (int i = 0; i < s.size(); ++i) { if (i != 0) { hashset.erase(s[i -
1]); } while (right + 1 < s.size() && !hashset.count(s[right+1])) {
hashset.insert(s[right + 1]); ++right; } // 第 i 到 rk 个字符是一个极长的无重复字符子串 ans =
max(ans, right - i + 1); } return ans; } }; int main() { string s = { "abdafa"
}; int return_value= Solution::lengthOfLongestSubstring(s); cout <<
return_value; }