●??哈希表理论基础
●??242.有效的字母异位词
●??349.?两个数组的交集
●??202.?快乐数
●??1.?两数之和
了解哈希表的内部实现原理，哈希函数，哈希碰撞，以及常见哈希表的区别，数组，set?和map。
当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。??这句话很重要，大家在
文章讲解：https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
class Solution {
public boolean isAnagram(String s, String t) {
//判断一个元素是否在什么中，考虑用哈希表法
//将第一个数组元素通过你哈希值，转成索引，保存在哈希表中
//将第二个数组元素通过哈希值得到索引，检查包不包含在哈爱惜表中，有就把它删掉，然后如果遍历哈希表得到值为0的话，那么就证明字母都是一样的
//哈希表已经是封装定义好的，直接拿来用就行
//比如说数值容量小的用数组,容量大用set,有value key我们用map
//这里是字母字符串，只有26个字母，那我i们就用数组，数组元素都默认是0
//先定义一个容量为26的数组，用来统计每一个字符串里面字母出现的频率，出现就在元素里面+1
int[] hash=new int[26];
for(int i=0;i<s.length();i++){
//字符串包含 unicode 字符怎么办，用当前的字符减去字母第一个a，如果是a-a的话，最终a就在下标0的位置
hash[s.charAt(i)-'a']++;
}
//遍历第二个字符串
for(int i=0;i<t.length();i++){
hash[t.charAt(i)-'a']--;
}//将出现在同一个索引下标的元素减减
//遍历hash数组，如果每个元素都是0，的话，证明两个字符串字母都是相同的
for(int i=0;i<hash.length;i++){
if(hash[i]!=0){return false;}
}
return true;
//字符串的长度是方法，要用length()
//数组的长度是属性，用.length
}
}
法一：数组
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
//因为1 <= nums1.length, nums2.length <= 1000
//先用数组解决
int[] hash1=new int[1000];
int[] hash2=new int[1000];
//创建一个集合
List<Integer> resList = new ArrayList<>();
//遍历第一个刷组，将每一个元素出现的频率存储到哈希表中，并且值都给到1
for(int i=0;i<nums1.length;i++){
//hash1[nums1[i]%1000]++;
hash1[nums1[i]]=1;
}
//遍历第二个数组,查看第二个数组的值在哈希表中位置的值是否等于1，如果等于1，证明是交集，那么我们存储到新的集合中（可以去重）
for(int i=0;i<nums2.length;i++){
if(hash1[nums2[i]]==1){
//证明是交集
resList.add(nums2[i]);
}
}
//转为HashSet进行去重
HashSet<Integer> set = new HashSet<>(resList);
return set.stream().mapToInt(x->x).toArray();
//遍历这些数值
}
}
法二：Set
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
return new int[0];
}
//用HashSet解决
Set<Integer> hashSet1=new HashSet<>();
Set<Integer> hashSet2=new HashSet<>();
//将两个数组的元素存进哈希表中
//这里遍历用for(int num:nums){输出num},这里的num就是每一个元素的值，而不是下标
for(int num:nums1){
hashSet1.add(num);
}
//判断数组2中的元素是否在1中包含过，如果包含过，则存进哈希表中
for(int num:nums2){
if(hashSet1.contains(num)){
hashSet2.add(num);
}
}
//那现在hashSet2就是存储着两个数组的交集了，HashSet也已经帮我们去重过了
//直接将set转为数组就好
return hashSet2.stream().mapToInt(x->x).toArray();
}
}
class Solution {
public boolean isHappy(int n) {
//判断一个数是不是什么，优先考虑到哈希
Set<Integer> hashSet1=new HashSet<>();
while(n!=1&&!hashSet1.contains(n)){
//如果结果不是1，那就把元素添加进哈希表中
hashSet1.add(n);
//继续去算每个位置上的数字的平方和
n=getNextNumber(n);
}
//如果和为1，那么就证明是快乐数
return n==1;
}
//求出每个位置的值，存进哈希表中
//如果result是大于1，就继续重复这一段（写成一个函数）
private int getNextNumber(int n){//每个位置上的数字的平方和
int result=0;
while(n>0){
//取个位数
int temp=n%10;
result+=temp*temp;
//舍去最后一位
n=n/10;
}
return result;
}
}
class Solution {
public int[] twoSum(int[] nums, int target) {
//请你在该数组中找出 和为目标值 target 的那 两个 整数
//考虑用到哈希
//我们用哈希表来存放我们遍历过的元素（元素值和下标）
//因为要找元素值和下标，所以我们考虑用哈希的map结构来存储
Map<Integer,Integer> hashmap=new HashMap<>();
//存放
int[] arr=new int[2];
if(nums == null || nums.length == 0){
return arr;
}
//我们遍历元素，遍历第一个元素的时候，就要想当前target-当前元素的值是否在map集合中出现过，如果出现过，就证明我们找到了
//如果没出现过，就继续往下遍历
for(int i=0;i<nums.length;i++){
int s=target-nums[i];
if(hashmap.containsKey(s)){
arr[0]=hashmap.get(s);
arr[1]=i;
break;
}
//往map里面存
hashmap.put(nums[i],i);
}
//遍历完了
return arr;
}
}