哈希表理论基础
题目建议： 大家要了解哈希表的内部实现原理，哈希函数，哈希碰撞，以及常见哈希表的区别，数组，set 和map。
什么时候想到用哈希法，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。 这句话很重要，大家在做哈希表题目都要思考这句话。
随想录知识点：
- 哈希表是根据关键码的值而直接进行访问的数据结构
- 一般哈希表都是用来快速判断一个元素是否出现集合里
- 直白来讲其实数组就是一张哈希表。哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素，如下图所示：
?常见的三种哈希结构：
- 数组
- set （集合）
- map(映射)
在C++中，set 和 map 分别提供以下三种数据结构：
?std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。
?同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）
- 使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。
- map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的
- 虽然std::set、std::multiset 的底层实现是红黑树，不是哈希表，但是std::set、std::multiset 依然使用哈希函数来做映射，只不过底层的符号表使用了红黑树来存储数据，所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。 map也是一样的道理。
?java里的HashMap ，TreeMap 都是一样的原理。可以灵活贯通
242.有效的字母异位词（数组）
题目建议：这道题目，大家可以感受到 数组 用来做哈希表 给我们带来的遍历之处
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。说明: 你可以假设字符串只包含小写字母
示例?1: 输入: s = "anagram", t = "nagaram" 输出: true
示例 2: 输入: s = "rat", t = "car" 输出: false
思路：
- 定义一个数组叫做record用来上记录字符串s里字符出现的次数，大小为26 就可以了，初始化为0，因为字符a到字符z的ASCII也是26个连续的数值。
- 只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
-
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++){
record[s.charAt(i)-'a']++;
}
for(int i=0;i<t.length();i++){
record[t.charAt(i)-'a']--;
}
for(int count:record){
if(count!=0){
return false;
}
}
return true;
}
} 重点语句：
- int[]?record?=?new?int[26];
- 注意字符串中提取长度是一个函数：for(int?i=0;i<s.length();i++)
- record[s.charAt(i)-'a']++;?
- for(int?count:record)，强循环，数组record不会改变，只是每次把record里面的值赋给临时变量count
349. 两个数组的交集（Set）
题目建议： 本题就开始考虑 什么时候用set 什么时候用数组，本题其实是使用set的好题，但是后来力扣改了题目描述和 测试用例，添加了 0 <= nums1[i], nums2[i] <= 1000 条件，所以使用数组也可以了，不过建议大家忽略这个条件。 尝试去使用set
给定两个数组，编写一个函数来计算它们的交集。说明： 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。
思路：
用Set不用数组来做这道题的原因有
- 不像上一题可以确定数组的大小为26，此题没有限制数值的大小，取法确定数组的长度
- Set可以去重
- 需要注意的是，不是遇到哈希就无脑Set，Set不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。在数据量大的情况，差距是很明显的
import java.util.HashSet;
import java.util.Set;
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
//这里的边界处理虽然不用也行，但是挺好的，值得学习
if(nums1.length==0 || nums2.length==0 || nums1==null || nums2==null){
return new int[0];
}
Set<Integer> set1 = new HashSet<>();
Set<Integer> reset = new HashSet<>();
for(int i:nums1){
set1.add(i);
}
for(int j:nums2){
if(set1.contains(j)){
reset.add(j);
}
}
//将结果集合转为数组
return reset.stream().mapToInt(x -> x).toArray();
}
}?重点语句：
包引入：import java.util.HashSet;? import java.util.Set;
定义一个Set：Set<Integer>? set = new HashSet<>();
一种比较好的边界判断：
if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
return new int[0];
}添加：set1.add(i);
判断j是否在set里：set1.contains(j);?
将结果集合转为数组：?return reset.stream().mapToInt(x->x).toArray();
202. 快乐数（Set）
题目建议： 这道题目也是set的应用，其实和上一题差不多，就是 套在快乐数一个壳子
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为? 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False
示例：
输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
思路：题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止
class Solution {
//取数值各个位上的单数之和
public int getsum(int n){
int sum =0;
int temp=0;
while(n!=0){
temp = n%10;
sum= sum+temp*temp;
n=n/10;
}
return sum;
}
public boolean isHappy(int n) {
int res=0;
Set<Integer> set = new HashSet<>();
set.add(n);
while(n!=1){
n = getsum(n);
if(set.contains(n)){
return false;
}else{
set.add(n);
}
}
return true;
}
}重点：
学会取数值各个位上的数?
1. 两数之和（Map）
题目建议：本题虽然是 力扣第一题，但是还是挺难的，也是 代码随想录中 数组，set之后，使用map解决哈希问题的第一题。
建议大家先看视频讲解，然后尝试自己写代码，在看文章讲解，加深印象
给定一个整数数组 nums?和一个目标值 target，请你在该数组中找出和为目标值的那?两个?整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
思路：需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适
用Map，而不用数组或者Set的原因
- 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
- set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。
此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value在保存数值所在的下标。
此题中，map中的存储结构为 {key：数据元素，value：数组元素对应的下标}
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
Map<Integer,Integer> map= new HashMap<>();
for(int i=0;i<nums.length;i++){
int temp=target-nums[i];
if(map.containsKey(temp)){
res[1]=i;
res[0]=map.get(temp);
}
map.put(nums[i],i);
}
return res;
}
}重点语句：
map.containsKey(temp)
获取key值为temp的value值：res[0]=map.get(temp)
添加：map.put(nums[i],i)
知识点总结
- int[]?record?=?new?int[26];
- 注意字符串中提取长度是一个函数：for(int?i=0;i<s.length();i++)
- record[s.charAt(i)-'a']++;?
- for(int?count:record)，强循环，数组record不会改变，只是每次把record里面的值赋给临时变量count
取数值各个位上的单数之和：
public int getsum(int n){
? ? ? ? int sum =0;
? ? ? ? int temp=0;
? ? ? ? while(n!=0){
? ? ? ? ? ? temp = n%10;
? ? ? ? ? ? sum= sum+temp*temp;
? ? ? ? ? ? n=n/10;
? ? ? ? }
? ? ? ? return sum;
}?Set:?
包引入：import java.util.HashSet;? import java.util.Set;
定义一个Set：Set<Integer>? set = new HashSet<>();
一种比较好的边界判断：
if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
return new int[0];
}添加：set1.add(i);
判断j是否在set里：set1.contains(j);?
将结果集合转为数组：?return reset.stream().mapToInt(x->x).toArray();
Map:?
添加：map.put(nums[i],i)
判断key值为temp的元素是否在map里：map.containsKey(temp)
获取key值为temp的value值：res[0]=map.get(temp)