哈希表

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; }

技术
今日推荐
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:[email protected]
QQ群:766591547
关注微信