链表的复习章节
哈希的概念和应用:https://programmercarl.com/哈希表理论基础.html#哈希函数
当我们想使用哈希法来解决问题的时候,我们一般会选择如下三种数据结构。
- 数组
- set (集合)
- map(映射)
这里数组就没啥可说的了,我们来看一下set。
Leetcode 242
时间复杂度 O(N)
空间复杂度O(1)
原本这道题我也使用的是hash表的形式进行解决,对比了这次的推荐答案,可以看出,推荐答案中的空间复杂度明显降低了。使用26个字母作为hash以外, 还有一个重要的点是在对于t检查时使用--的形式,最后进行判断是否全部为0.
leetcode349
可以用set来解决问题,对比两个数组中的元素的差异性。 尝试用java写代码
先用set存储nums1中的那些元素,然后用nums2进行比对,将出现过的放置在数组中并进行return。
Java中的stream很有意思, 一个个转换的格式 A.stream().mapToInt(x->x).toArray()
拓展
那有同学可能问了,遇到哈希问题我直接都用set不就得了,用什么数组啊。
直接使用set 不仅占用空间比数组大,而且速度要比数组慢,set把数值映射到key上都要做hash计算的。
不要小瞧 这个耗时,在数据量大的情况,差距是很明显的。根据题目描述可以使用1005左右的数组进行存储和传递
Leetcode 350 类似题
已解决
https://leetcode.com/problems/intersection-of-two-arrays-ii/solutions/3543253/java-hash-table/
Leetcode202
https://leetcode.com/problems/happy-number/solutions/3543306/hash-table/
Leetcode 1 Two Sum
使用hashmap进行解决, 在java中定义方式,判断方式,读取,输入方式
Map<Integer, Integer> map = new HashMap<>();
map.containsKey(temp)
map.get(temp)
map.put(nums[i], i);