LeetCode Hash 刷题模板
2022-03-15 算法
数学概念
在数学中，单射（injection）、满射（surjection）和双射（bijection）是描述函数之间关系的重要概念，通常用于描述两个集合之间的映射关系。
单射
对于集合 A 中的每个不同的元素，在集合 B 中都有唯一的映射元素。
满射
对于集合 A 中的每个不同的元素，在集合 B 中都至少有一个的映射元素。
双射
同时满足单射和满射, 对于集合 A 中的每个不同的元素，在集合 B 中都有唯一的映射元素，同时，对于集合 B 中的每个不同的元素，在集合 A 中都有唯一的映射元素，也就是集合 A 和 集合 B 中的元素是一一对应的。
哈希类型题目
将 Hash 类题目从本质进行分类，基本可以分为单射、满射、双射映射问题。
Hash 类型题目应该是所有题型中最简单的了，尤其是使用 Go 写过业务代码之后，这种体验应该会更深 ~ 单纯的 Hash 类型题目基本都是简单类题目，所以整体的刷题体验还是很愉快的。
但是有一个比较踩坑的地方在于：虽然很多题目都可以使用 Hash 来开始暴力解题，但是这些题目的考点都不在 Hash 上面，毕竟 Hash 带来的额外空间开销是不可忽视的，和位运算一样，Hash 也属于低频考题，如果面试中遇到的题目除了 Hash 之外想不到其他解题方法，可以先使用 Hash 给出题解答案，然后根据面试官的反馈来确定下一步。
Golang Set
Go 语言中没有内置的 Set 数据类型，所以遇到需要使用 Set 的场景，需要自定义一个实现，下面给出一个通用的模板。
// 集合初始化
set := make(map[int]struct{})
// 向集合插入一些数据
for i := range nums {
set[nums[i]] = struct{}{}
}
// 查找某个元素是否存在于集合中
if _, ok := set[v-1]; ok {
...
}
空间使用技巧
如果题目参数给出了数值范围，例如纯小写字母、纯大写字母，这时候可以使用对应长度数组代替 Map, 提升细微的时间效率和空间效率，下面列举了一些典型的使用场景。
参数由任意小写 (大写) 字母组成
可以直接定义一个长度为 26 的数组来充当 Map 数据类型：
m := [26]int{}
参数由任意 ASCII 字符组成
可以直接定义一个长度为 128 的数组来充当 Map 数据类型：
m := [128]int{}
参数由任意 0 - 9 数字组成
可以直接定义一个长度为 10 的数组来充当 Map 数据类型：
m := [10]int{}
💡 典型题目
前文中提到，Hash 类型题目基本可以归类为单射、满射、双射映射问题，那么解题过程中唯一需要确认的就是：输入集合是什么？输出集合是什么？ 大多数问题直接套用这个模板即可，解题过程就和写业务代码差不多。
1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
## 示例来自：https://leetcode.cn
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
快速套模板：
- 确定题型：这是一个根据输出集合求解输入集合的问题
- 输出集合：参数数组元素集合 (只要集合不为空就存在题目要求的解)
- 输入集合：参数 target - 参数数组各元素的差 形成的集合
// 题解代码
func TwoSum(nums []int, target int) []int {
m := make(map[int]int)
for i, num := range nums {
if diff, ok := m[target-num]; ok {
return []int{diff, i}
}
m[num] = i
}
return []int{}
}
2. 赎金信
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。magazine 中的每个字符只能在 ransomNote 中使用一次。
## 示例来自：https://leetcode.cn
示例 1：
输入：ransomNote = "a", magazine = "b"
输出：false
示例 2：
输入：ransomNote = "aa", magazine = "ab"
输出：false
示例 3：
输入：ransomNote = "aa", magazine = "aab"
输出：true
快速套模板：
- 确定题型：求解两个字符串是否为满射
- 输出集合：参数 magazine 字符串
- 输入集合：参数 ransomNote 字符串
func canConstruct(ransomNote string, magazine string) bool {
m := [26]int{}
for _, char := range magazine {
m[char-'a']++
}
for _, char := range ransomNote {
m[char-'a']--
if m[char-'a'] < 0 {
return false
}
}
return true
}
3. 同构字符串
给定两个字符串 s 和 t ，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
## 示例来自：https://leetcode.cn
示例 1:
输入：s = "egg", t = "add"
输出：true
示例 2：
输入：s = "foo", t = "bar"
输出：false
示例 3：
输入：s = "paper", t = "title"
输出：true
快速套模板：
- 确定题型：求解两个字符串是否为双射，函数为字符串中每个字符的位置对应
- 输出集合：参数 s 中每个字符出现的位置
- 输入集合：参数 t 中每个字符出现的位置
func isIsomorphic(s string, t string) bool {
sMap := [128]int{}
tMap := [128]int{}
// 只需要记录连续字符的位置相对性
for i := range s {
if sMap[s[i]] != tMap[t[i]] {
return false
} else {
if sMap[s[i]] == 0 {
// 更新字符位置为最新索引 + 1
// i + 1 是为了避免 map value 默认值为 0 引起的错误
sMap[s[i]] = i + 1
tMap[t[i]] = i + 1
}
}
}
return true
}
4. 单词规律
给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。
## 示例来自：https://leetcode.cn
示例1:
输入: pattern = "abba", s = "dog cat cat dog"
输出: true
示例 2:
输入:pattern = "abba", s = "dog cat cat fish"
输出: false
示例 3:
输入: pattern = "aaaa", s = "dog cat cat dog"
输出: false
快速套模板：
- 确定题型：求解两个字符串中是否为双射，函数为单个字符和多个字符的的位置对应
- 输出集合：参数字符串 pattern
- 输入集合：参数字符串 s
func wordPattern(pattern string, s string) bool {
// 双射解题
wordToChar := make(map[string]byte)
charToWord := make(map[byte]string)
words := strings.Split(s, " ")
if len(pattern) != len(words) {
return false
}
for i, word := range words {
char := pattern[i]
// 如果不满足双射条件，直接返回
if wordToChar[word] > 0 && wordToChar[word] != char {
return false
}
if len(charToWord[char]) > 0 && charToWord[char] != word {
return false
}
wordToChar[word] = char
charToWord[char] = word
}
return true
}
