当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。
参考：https://gitee.com/programmercarl/leetcode-master
- 242. 有效的字母异位词
- 1002. 查找共用字符
- 349. 两个数组的交集
- 202. 快乐数
- 1. 两数之和
- 454. 四数相加 II
- 383. 赎金信
方法一：排序
class Solution {
public boolean isAnagram(String s, String t) {
if(s.length()!=t.length()) return false;
char[] str1=s.toCharArray();
char[] str2=t.toCharArray();
Arrays.sort(str1);
Arrays.sort(str2);
return Arrays.equals(str1,str2);
}
}
方法二：哈希
因为字符串只包含小写字母，所以维护一个26位的数组，遍历s，字母对应下标的数组值+1；遍历t，字母对应下标的数组值-1；最后数组不全为0说明不相等
class Solution {
public boolean isAnagram(String s, String t) {
if(s.length()!=t.length()) return false;
int[] table = new int[26];
for(int i=0;i
1002. 查找共用字符
字符串全由小写字符组成，所以维护一个26位的数组res，再维护一个26位的数组temp，两个字符串分别存入这两个数组，两两比较，相同的留在res，循环直到字符串比完
class Solution {
public List commonChars(String[] words) {
int[] minfreq=new int[26];
Arrays.fill(minfreq,Integer.MAX_VALUE);
for(String word:words){
int[] freq=new int[26];
for(int i=0;i ans = new ArrayList();
for(int i=0;i<26;i++){
for(int j=0;j
349. 两个数组的交集
本题不再是26个小写字母，而是所有整数，不能使用数组来构造哈希，只能用Set
用两个集合来存储两个数组中的元素，再遍历较小集合中的元素，判断是否存在于另一元素中，如果存在，加入答案
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set set1 = new HashSet();
Set set2 = new HashSet();
for(int num:nums1){
set1.add(num);
}
for(int num:nums2){
set2.add(num);
}
return getIntersection(set1,set2);
}
public int[] getIntersection(Set set1,Set set2){
if(set1.size()>set2.size())
return getIntersection(set2,set1);
Set intersectionSet = new HashSet();
for (int num:set1){
if(set2.contains(num))
intersectionSet.add(num);
}
int[] res = new int[intersectionSet.size()];
int index=0;
for(int num:intersectionSet){
res[index++] = num;
}
return res;
}
}
202. 快乐数
情景一：拆分后平方相加，得到1；
情况二：拆分后平方相加，一直在一个循环链表里循环
情况三：拆分后平方相加，无限变大 —— 不可能
因为输入最大为2147483647，拆分后平方相加为260，即：数字位数越多，计算后越小，所以不可能无限变大
算法分为两部分：
1.计算拆分后平方相加的下一数字
2.判断是否在循环内（用Set：当数字不在Set里且！=1时加入Set，如果数字形成循环链表就不会进入Set，判断数字是否==1）
class Solution {
public int getNext(int n){
int res=0;
while(n>0){
int d=n%10;
res+=d*d;
n=n/10;
}
return res;
}
public boolean isHappy(int n) {
Set seen = new HashSet<>();
while (n != 1 && !seen.contains(n)) {
seen.add(n);
n = getNext(n);
}
return n == 1;
}
}
1. 两数之和
数组中的元素加入哈希，如果target-nums[i]在Set中，则返回两者的下标
因为要同时存储值和下标，用Map
class Solution {
public int[] twoSum(int[] nums, int target) {
Map hashtable = new HashMap();
for(int i=0;i
454. 四数相加 II
本题只要求元组个数，不要元组下标，可以用分组来解决问题
将A，B分为一组，C，D分为一组
双重循环遍历A，B，将A[i]+B[j]作为键，它们的数量作为值存入Map
再双重遍历C，D，如果有0-（A[i]+B[j]）的，ans++
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map countAB = new HashMap();
for(int u:nums1){
for(int v:nums2){
countAB.put(u+v,countAB.getOrDefault(u+v,0)+1);
}
}
int ans=0;
for(int u:nums3){
for(int v:nums4){
if(countAB.containsKey(-u-v))
ans+=countAB.get(-u-v);
}
}
return ans;
}
}
383. 赎金信
字符串只有小写字母，可以用数组构造哈希表
两个字符串，构造一个哈希表，杂志字母+，赎金信字母-，最后数组全部大于等于0返回true
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] table = new int[26];
for(int i=0;i 
