哈希表算法（1）

哈希表相关算法题 | 代码随想录_哈希表

什么时候可能会用到哈希表？

给一个元素，需要判断它是否在一个集合中出现过，通常就需要用哈希表了。

在 Go 语言中，可以使用数组或者 map 来解题。（例如数组下标存元素、map 的 key 存数据……）

数据量小用数组；数据量散用 map 。

例如要处理 0, 5, 1000000 这三个数，如果用数组下标需要开辟很大的数组，但要处理的数据只有3个，会造成很大的空间浪费，这时使用 map 合适。像 242.有效的字母异位词 中用数组就比较方便。如果用 map 的话还需要进行哈希运算，用数组比较省。

242.有效的字母异位词

242. 有效的字母异位词

简单

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
提示:

1 <= s.length, t.length <= 5 * 104

s 和 t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

哈希表

数据比较小用数组，~~数据比较大用set~~，数据比较散用map

构建一个大小为26的数组 hash ，遍历第一个单词 s ，出现一个字母，对应位置+1，a对应0。

再遍历第二个单词 t ，并对对应位置元素-1。

最后遍历 hash，如果出现非0元素，那么这两个单词一定不是字母异位词。（力扣上认为 abc 和 abc 也是字母异位词）

func isAnagram(s string, t string) bool {
    hash := [26]int{}
    for i := 0; i < len(s); i++ {
        hash[s[i] - 'a']++
    }
    for i := 0; i < len(t); i++ {
        hash[t[i] - 'a']--
    }
    for i := 0; i < 26; i++ {
        if hash[i] != 0 {
            return false
        }
    }
    return true
}

349. 两个数组的交集

349. 两个数组的交集

简单

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。

示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
提示：

1 <= nums1.length, nums2.length <= 1000

0 <= nums1[i], nums2[i] <= 1000

思路：哈希表

哈希表—map

func intersection(nums1 []int, nums2 []int) []int {
    hash := make(map[int]int)
    index := 0
    var result []int
    for i := 0; i < len(nums1); i++ {
        hash[nums1[i]] = index
        index++
    }
    for i := 0; i < len(nums2); i++ {
        if _, ok := hash[nums2[i]]; ok {
            // 先写入 result
            result = append(result, nums2[i])
            // 删除 hash 中这个数值，避免之后 result 元素重复
            delete(hash, nums2[i])
        }
    }
    return result
}

其实一开始写的版本是，每次循环判断 hash 中是否出现过 nums[2]，逻辑很不清晰。

展开查看


    func intersection(nums1 []int, nums2 []int) []int {
        hash := make(map[int]int)
        index := 0
        var result []int
        for i := 0; i < len(nums1); i++ {
            hash[nums1[i]] = index
            index++
        }
        for i := 0; i < len(nums2); i++ {
            if _, ok := hash[nums2[i]]; ok {
                // 写入切片前先判断是否会重复
                exist := false
                for j := 0; j < len(result); j++ {
                    if result[j] == nums2[i] {
                        exist = true
                        // 也可以检测到在 hash 中存在，就删掉 hash 中的这个值。就是这一步遍历的可能多一点。
                        break
                    }
                }
                if !exist {
                    result = append(result, nums2[i])
                }
            }
        }
        return result
    }

哈希表—数组

力扣上新增了以下条件，现在可以用数组求解了。

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

用数组的下标来存储 nums1 的元素，如果该元素出现过则 hash 中该下标对应的值设为1（顺便可以去重）。

然后用 nums2 中的元素去查询 hash，如果查到了就放进 result，顺便把 hash 对应的值改为 0 实现 result 去重。

func intersection(nums1 []int, nums2 []int) []int {
    hash := [1001]int{}
    result := []int{}
    for i := 0; i < len(nums1); i++ {
        // 用下标存储 nums1 的元素
        hash[nums1[i]] = 1
    }

    for i := 0; i < len(nums2); i++ {
        // 判断 hash 中是否出现过 nums2[i]
        if hash[nums2[i]] == 1 {
            result = append(result, nums2[i])
            hash[nums2[i]] = 0
        }
    }
    return result
}

# 哈希表算法（1）