代码随想录——哈希表 刷题记录

哈希表

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。
但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

242.有效的字母异位词

用哈希表存储每个字母及对应的数量，代码随想录用了26字母的数组解决，我用的HashMap记录s，再遍历t，减掉t中字母后得到最后的HashMap

349.两个数组的交集

HashMap和HashSet的关系

1. HashSet底层是采用HashMap实现的。HashSet 的实现比较简单，HashSet 的绝大部分方法都是通过调用 HashMap 的方法来实现的，因此 HashSet 和 HashMap 两个集合在实现本质上是相同的。
2. HashMap的key就是放进HashSet中对象，value是Object类型的。
3. 当调用HashSet的add方法时，实际上是向HashMap中增加了一行(key-value对)，该行的key就是向HashSet增加的那个对象，该行的value就是一个Object类型的常量

// 创建，HashSet是无序集合
Set<Integer> set1 = new HashSet<>();
// 遍历
int i = 0;
for (int j: ansSet){
	ans[i] = j;
    i++;
}

Set里的元素不重复！！！

383.赎金信

可以直接用哈希表，也可以用长为26的数组计数，用数组比较省时高效。

49.字母异位词分组

List是个接口，并不能直接用来实例化，如果要使用，必须去实例化List的实现类

List<String> list = new ArrayList<String>();

哈希表键：字符串，值：字符串对应异位词的list

438.找到字符串中所有字母异位词

判断两个hashmap是否有包含关系时，不要把形参删除或添加，会改变原始hashmap的值
有点难，可以回头再做一遍

349.两个数组的交集

不计数只出现一次可以用Set

350.两个数组的交集II

由于Set元素不重复，需要重复且长度不确定时可以用List，但创建对象需要用ArrayList。

202.快乐数

如果有无限循环的情况，那就是结果之前有出现过，可以用Set存储每一轮的和。

1.两数之和

可以往Map中添加未配对的数和其下标，key为元素，value为对应数组下标，计算每个值对应的另一个加数，在Map中查找加数即可。

454.四数相加II

和上题类似，不过可以统计前两个数组的和记录到Map中，再求后两个数组的和，在Map中找另外的加数。

15.三数之和

采用双指针法，确定遍历的i和left=i+1，right=len-1，进而确定三位数
注意去重时要与前面的数字对比，不要和后面的对比
可以重做

• 把数字转化成数组的方法

Arrays.asList(nums[i], nums[left], nums[right])

18.四数之和

和上题类似，不过多加一个遍历第二个数的循环，注意(long)强制类型转换