面试算法入门-Hash

发表于 | 分类于

写在前面

面试准备算法篇之一。Hash表。

Hash算法

哈希表（Hash Table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做哈希函数，存放记录的数组称做哈希表。

一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名 xx 到首字母 F(x)F(x) 的一个函数关系），在首字母为 WW 的表中查找 “王” 姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母” 是这个例子中哈希函数的函数法则 F()F()，存放首字母的表对应哈希表。关键字和函数法则理论上可以任意确定。

哈希表是使用 O(1)O(1) 时间进行数据的插入删除和查找，但是哈希表不保证表中数据的有序性，这样在哈希表中查找最大数据或者最小数据的时间是 O(N)O(N) 实现。

经典题目(leetcode)

两数之和

1
2
3
4
5
6
7
8
9
给定一个整数数组 nums 和一个目标值 target，
请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。


示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let hashMap = {}, res=[]
    nums.some((num, index)=>{
        if(hashMap[target-num] !== undefined) {  // 使用some可以减少遍历次数
            res = [index, hashMap[target-num]]
            return true
        }
        hashMap[num] = index // 后负值可以不用担心角标重复
    })
    return res
};

解题思路

Hash表主要是做映射解题思路。对于该题来说。我们定义一个hashMap映射集合。判断当我们映射集合中存在target-num(当前角标值)值的元素的时候。即算找到正确解。

需要注意的是遍历时用some，当return为true时自动跳出。先判断是否有符合条件的值，再给hashMap负值可以免去当前角标重复判断。

两个数组的交集 II

1
2
3
4
5
6
7
8
9
给定两个数组，编写一个函数来计算它们的交集。

示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
    let hashMap1 = {}, res = []
    nums1.forEach((num)=> {
        hashMap1[num] ? hashMap1[num]++ : hashMap1[num] = 1 
    })
    nums2.forEach((num)=> {
        if(hashMap1[num]) {
            res.push(num)
            hashMap1[num] --
        }
    })
    return res
};

解题思路

定义hashMap存下nums1中的数字出现的次数。在nums2遍历的时候动态删除，同时在res数组中添加相应的数字即可。