hash

本篇博客只记录刷题思路不记录具体代码，用于本人快速回顾
题目来源代码随想录
今天还在喝中药🤒

有效的字母异位词

服了每次都想不到用数组

虽然还是要两次for罢了，但起码复杂度还是O(n)

优化剪枝：

  1. 先判断长度是否相同
  2. 我靠好妙，官方解答是第一次for数组确定value，第二次for数组 if数组==0；还有一种解法是第一次for1确定数组value，第二次for减去s2的数组再if ==0，这就就可以只遍历length* 2而不是26* 2【但如果是长字符的话效率不高】但实际运行并没有快很多🤔
  3. 还有一种方法：toCharArray后sort再equals，但感觉有点过于依赖API了

看题解下的评论也真好！！！

两个数组的交集

这个主要是观察题干发现：1. 要求不重复 2. 数字范围没有限制

所以就用set解决

还有一个难点是set转数组了

快乐数

额老师我是真的没想到居然使用hash存结果啊

没什么思路

首先 求和不难想到，但是没想到while的跳出条件

条件就是当前和是之前存在的，这样的话就会一直循环

两数之和

梦开始的地方

  1. 快速查找是否存在——用哈希表
  2. 涉及到对应关系——用map，key存当前数，value存当前数位置【因为最后要返回的是这个】，相关方法containsKey(key)、put(key，value)

四数相加Ⅱ

和四数之和最大的区别就是不用考虑去重，只用算次数（真的简便很多！

面对多元素我们的思路是抽丝剥茧

先两层for计算两个数组的元素之和放进map，key存sum，value存次数

再两层for统计剩余两个元素之和，在map中查找是否存在

相关方法：getOrDefault(value,defaultvalue)

赎金信

和《有效的字母异位词》几乎一样，就是题目有点新奇

三数之和

相当于target = 0，但是哈希表做这道题很多东西要处理

不如双指针，先确定一个数，另外两个指针找两数之和

直接上思路（因为没想完善）

  1. 因为去重，所以肯定得先排序，排序是去重的基础
  2. for遍历第一个数
  3. 左右指针开始遍历，while指针没有相遇，求和
  4. 如果==target，就加进list，❗同时要while更新左右指针去重❗

四树之和

和三数之和的思路很像

必须两层for +左右指针

注意判断第一个组合和最后一个组合是否>target，用来剪枝