哈希表 很重要
哈希表
哈希表 场景 一般哈希表都是用来快速判断一个元素是否出现集合里
一般来说 数组模拟 哈希set 哈希map 不同的场景
当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。
但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。
如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法！
Leetcode242 有效的字母异位词
题目链接
若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
用哈希表 去保存字符串的次数 如果最后归0 则是异位词
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 i = 0;i<record.length;i++){if(record[i]!=0){return false;}}return true;}
}Leetcode349 两个数组的交集
题目链接
给定两个数组 返回交集 元素唯一
思想：看到元素唯一 可以想到用哈希表的set结构 先 设置一个哈希表存储第一个数组
然后设置一个结果哈希表，遍历第二个数组的时候 如果第一个哈希表中存在 那么添加到结果哈希表中即可
注意 hashset用法 以及 流的使用
class Solution {public int[] intersection(int[] nums1, int[] nums2) {if(nums1==null||nums2==null||nums1.length==0||nums2.length==0){return new int[0];}Set<Integer> reset = new HashSet<>();Set<Integer> set1 = new HashSet<>();for(int i = 0;i<nums1.length;i++){set1.add(nums1[i]);}for(int i = 0;i<nums2.length;i++){if(set1.contains(nums2[i])){reset.add(nums2[i]);}}return reset.stream().mapToInt(x -> x).toArray();}
}Leetcode202 快乐数
题目链接
注意此题 也可能是 无限循环 但始终变不到 1 非常关键
会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！
当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。
这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。
class Solution {public boolean isHappy(int n) {Set<Integer> sum = new HashSet<>(); while(n!=1&& !sum.contains(n)){sum.add(n);n = getNext(n);}if(n==1){return true;}else{return false;}}public int getNext(int n){int a = 0;while(n>0){int temp = n%10;temp = temp*temp;a+=temp;n/=10;}return a;}
}Leetcode1 两数之和
题目链接
经典哈希表题目
理清思路 用哈希表存储元素和他的需要的值
再强调一下 什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。
map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的（也就是相加等于target）
class Solution {public int[] twoSum(int[] nums, int target) {int[] res = new int[2];Map<Integer, Integer> map = new HashMap<>();if(nums == null|| nums.length ==0){return res;}for(int i = 0;i<nums.length;i++){int a = target - nums[i];if(map.containsKey(a)){res[0] = i;res[1] = map.get(a);return res;}map.put(nums[i],i);}return res;}
}
