哈希表

Date:

哈希表经典题: 哈希表、计数、查找等题目的核心思路


哈希表

当要判断a是否在b中出现过? a和b是否有重复时,都可以想到用哈希表。用b建表,用a查表即可判断。 Array , Map 的实现,有限的元素个数就用Array,因为快。

242. 有效的字母异位词

基础的哈希题,先建表再查表

349. 两个数组的交集

基础的哈希题,先建表再查表

1. 两数之和

找数组中两个和为t的元素,那就遍历数组,遍历到x,那就看 (t-x)是否出现过,如果出现过那就返回x的下下标和我们存起来的t-x的下标

  1. 此处有个小坑,hash查表的结果为0时,if(0)就会无法进入循环,需要if(idx!=null) 或者用js map中的map.has(“xx”)

2. 四数相加

还比较简单,先两层for循环,把问题转换为找(a + b)+(c + d)=0的四元组,

  1. 注意:想想hash表的key和value应该是什么, 计数的时候不要计错了

15. 三数之和

用双指针实现:通过升序排序后,用类似滑动窗口的思想查找。[current, left, right] 1.current作为循环基数 2.left = current + 1; right = length - 1 3.因为是递增的,如果sum>0则right–,如果sum<0则left++ 4.主要恶心的是去重,需要在插入的时候添加去重逻辑,否则在结果集里去重会超时。

16. 四数之和

和三数之和同理,升序排序 + 双指针(类滑动窗口)

  1. 在三数之和的外层再套一层循环
  2. 此题的target并不是恒为0, 所以不能通过第一个元素大于target就跳出, 因为即便升序排序了,负数+负数仍然会更小