刷题计划 day5 哈希表上
⚡刷题计划day5继续，可以点个免费的赞哦~
今天开启哈希表刷题专题，往期可看专栏，关注不迷路，
您的支持是我的最大动力🌹~
目录
哈希表理论基础简述
哈希表
哈希表（hash table），又称散列表，它通过建立键 key 与值 value 之间的映射，实现高效的元素查询。具体而言，我们向哈希表中输入一个键 key ，则可以在 O(1) 时间内获取对应的值 value 。
哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。
元素查询效率对比：
例如要查询一个名字是否在这所学校里。
要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1)就可以做到。
我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。
将学生姓名映射到哈希表上就涉及到了hash function ，也就是哈希函数。
哈希函数
哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间。
将键通过哈希函数转换为数组索引。一个好的哈希函数应该能够将键分布到数组的各个位置，以减少冲突。
输入一个 key ，哈希函数的计算过程分为以下两步。
-
通过某种哈希算法
hash()计算得到哈希值。 -
将哈希值对桶数量（数组长度）
capacity取模，从而获取该key对应的数组索引index。
index = hash(key) % capacity通过取模后的值，比如hash(key) % capacity = 36 ，那么就会映射到了索引下标 36的位置，可结合图理解：
哈希碰撞（哈希冲突）：
通常情况下哈希函数的输入空间远大于输出空间，因此理论上哈希冲突是不可避免的。比如，输入空间为全体整数，输出空间为数组容量大小，则必然有多个整数映射至同一桶索引。
如图所示，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞。
通常解决方法有：链地址法（每个数组位置存储一个链表，所有映射到该位置的键值对都存储在这个链表中）和开放寻址法（寻找空的数组位置来存储）。
题目一：242. 有效的字母异位词
leetcode：242. 有效的字母异位词
(https://leetcode.cn/problems/valid-anagram/description/)
暴力解法就不介绍了
数组就是一个简单哈希表，题目中字符串只有小写字符，那么就可以定义一个record数组，来记录字符串s里字符出现的次数。
新定义record数组大小26就可以，代表字符a到字符z的26个连续的ASCII值
在遍历字符串s1时，对于数组下标 s[i] - ‘a’（字母对应相对数值），出现一次record数组就加1；遍历完后record便记录了s1串每个字符出现的次数
接下来遍历字符串s2，对应下标出现一次，便将record数组对应减1；
两字符串都遍历完成后，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。
如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。
代码如下：
class Solution {
public boolean isAnagram(String s, String t) {
int[] record = new int[26];
for(int i=0;i<s.length();i++){ // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
record[s.charAt(i)-'a']++;
}
for (int i=0;i<t.length();i++){
record[t.charAt(i)-'a']--;
}
for (int i=0;i<record.length;i++){
if(record[i] !=0){ // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
return false;
}
}
return true; // record数组所有元素都为零0，说明字符串s和t是字母异位词
}
}题目二：383. 赎金信
leetcode：383. 赎金信
(https://leetcode.cn/problems/ransom-note/description/)
因为题目说只有小写字母，那可以采用空间换取时间的哈希策略，用一个长度为26的数组来记录magazine里字母出现的次数。
和上一题思路差不多，区别点在于对于record数组的条件的判断，
record数组减后值如果<0，则说明减多了，不能全部包含。
一些同学可能想，用数组干啥，都用map完事了，其实在本题的情况下，使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。 所以数组更加简单直接有效。
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] record = new int[26];
for (int i=0;i<magazine.length();i++){
record[magazine.charAt(i)-'a']++;
}
for (int i=0;i<ransomNote.length();i++){
record[ransomNote.charAt(i)-'a']--;
}
for (int i=0;i<record.length;i++){
if(record[i]<0){
return false;
}
}
return true;
}
}题目三：349. 两个数组的交集
leetcode：349. 两个数组的交集
(https://leetcode.cn/problems/intersection-of-two-arrays/description/)
此题输出结果唯一，所以结果需要去重
暴力的解法时间复杂度是O(n^2)，使用哈希时间复杂度可以降低到 O(m+n)
大体思路：首先遍历num1，将其元素存入set1集合。再遍历num2，判断元素是否出现在set1集合中，如果存在，则加元素加入set2集合。之后再把数组转换为集合即可
代码如下
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<Integer>();
Set<Integer> set2 = new HashSet<Integer>();
//遍历 nums1
for(int num1: nums1){
set1.add(num1);
}
//遍历nums2，判断哈希表中是否存在该元素
for(int num2: nums2) {
if (set1.contains(num2)) {
set2.add(num2);
}
}
int[] arr = new int[set2.size()];
int j=0;
for(int i:set2){
arr[j++] = i;
}
return arr;
}
}有没有发现，今天的三道题都是同类型的题，是不是思路都差不多。相同类型的题刷多了，你就会发现，最后其实在你脑子里记住的不是实现这道题的代码，而是解这道题的思路。
原文地址：https://blog.csdn.net/weixin_72499901/article/details/140708133
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！