哈希表
Date:
哈希表经典题: 哈希表、计数、查找等题目的核心思路
哈希表
当要判断a是否在b中出现过? a和b是否有重复时,都可以想到用哈希表。用b建表,用a查表即可判断。 Array , Map 的实现,有限的元素个数就用Array,因为快。
242. 有效的字母异位词
基础的哈希题,先建表再查表
349. 两个数组的交集
基础的哈希题,先建表再查表
1. 两数之和
找数组中两个和为t的元素,那就遍历数组,遍历到x,那就看 (t-x)是否出现过,如果出现过那就返回x的下下标和我们存起来的t-x的下标
- 此处有个小坑,hash查表的结果为0时,if(0)就会无法进入循环,需要if(idx!=null) 或者用js map中的map.has(“xx”)
2. 四数相加
还比较简单,先两层for循环,把问题转换为找(a + b)+(c + d)=0的四元组,
- 注意:想想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. 四数之和
和三数之和同理,升序排序 + 双指针(类滑动窗口)
- 在三数之和的外层再套一层循环
- 此题的target并不是恒为0, 所以不能通过第一个元素大于target就跳出, 因为即便升序排序了,负数+负数仍然会更小