算法学习：哈希表

参考代码随想录：哈希表理论基础

关于哈希表这种数据结构，这里也不再多说，参考笔记：哈希表

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构：

  • 数组
  • set （集合）
  • map(映射)

这里不再多说，直接看几个LeetCode上的题目。

有效的字母异位词

代码随想录：

LeetCode 242. 有效的字母异位词

数组就是简单的哈希表，但是数组的大小可不是无限开辟的。

数组

全都是小写字母，所以用一个26长度的数组即可表示字符串（结合ASCII码，这种处理已经很常见了）。

不用多说什么，直接看代码吧。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
func isAnagram(s string, t string) bool {
	lengthS, lengthT := len(s), len(t)
	if lengthS != lengthT {
		return false
	}
	sArr, tArr := [26]int{}, [26]int{}
	for i := 0; i < lengthS; i++ {
		sArr[s[i]-'a']++
		tArr[t[i]-'a']++
	}
	return sArr == tArr // go中，数组是可以直接比较的
}

相关题目推荐：

这些例题可以参考自己的刷题笔记。

两个数组的交集

代码随想录：

LeetCode 349. 两个数组的交集

如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

HashSet

之前在项目中已经写过切片之间的交集并集差集了，思路不用多说。

求差集的话，HashSet就够了。这里提一下go中的set。go没有set这个数据结构，但是我们可以通过定义map并指定value为，空结构体struct{}来实现set。因为在Go中，空结构体struct{}是不占任何内存的。

在Go中，空结构体struct{}是不占任何内存的。因为空结构体不占据内存空间，因此被广泛作为各种场景下的占位符使用。一是节省资源。二是空结构体本身就具备很强的语义，即这里不需要任何值，仅作为占位符。（其中经典的用法就是用来实现集合Set。这里可以引申讲讲Go空结构体struct{}）

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func intersection(nums1 []int, nums2 []int) []int {
	set1 := make(map[int]struct{}, 0)
	set2 := make(map[int]struct{}, 0)
	res := make([]int, 0)
	// 两个切片的去重操作
	for _, num := range nums1 {
		if _, ok := set1[num]; !ok { // map中没有这个元素，添加
			set1[num] = struct{}{}
		}
	}
	tmp := make([]int, 0) // 去重后的nums2
	for _, num := range nums2 {
		if _, ok := set2[num]; !ok { // map中没有这个元素，添加
			set2[num] = struct{}{}
			tmp = append(tmp, num)
		}
	}
	// 遍历去重后的nums2切片
	for _, num := range tmp {
		if _, ok := set1[num]; ok { // map中有这个元素，说明是两个切片的交集
			res = append(res, num)
		}
	}
	return res
}

其实感觉这样写代码还是有点臃肿的。可以使用一个set来实现，注意在遍历nums2时要delete键值对即可。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func intersection(nums1 []int, nums2 []int) []int {
	set := make(map[int]struct{}, 0)
	res := make([]int, 0)
	for _, num := range nums1 { // 遍历nums1获取set
		if _, ok := set[num]; !ok { // 元素不存在map中，添加
			set[num] = struct{}{}
		}
	}
	for _, num := range nums2 { // 遍历nums2，根据上面得到的set就能获取交集
		if _, ok := set[num]; ok { // 元素存在map中，说明是交集的元素
			res = append(res, num)
			delete(set, num) // 删除这个键值对，避免交集res中出现重复元素
		}
	}
	return res
}

相关题目推荐：

这些例题可以参考自己的刷题笔记。

快乐数

代码随想录：

LeetCode 202. 快乐数

该用set的时候，还是得用set。

HashSet

参考官方题解

根据我们的探索，我们猜测会有以下三种可能：

  1. 最终会得到1
  2. 最终会进入循环
  3. 值会越来越大，最后接近无穷大（后面会说明这种情况永远不会发生）

第三个情况比较难以检测和处理。我们怎么知道它会继续变大，而不是最终得到 11 呢？我们可以仔细想一想，每一位数的最大数字的下一位数是多少。

Digits Largest Next
1 9 81
2 99 162
3 999 243
4 9999 324
13 9999999999999 1053

对于3位数的数字，它不可能大于243。这意味着它要么被困在243以下的循环内，要么跌到1。4位或4 位以上的数字在每一步都会丢失一位，直到降到3位为止。所以我们知道，最坏的情况下，算法可能会在 243 以下的所有数字上循环，然后回到它已经到过的一个循环或者回到1。但它不会无限期地进行下去，所以我们排除第三种选择。

即使在代码中你不需要处理第三种情况，你仍然需要理解为什么它永远不会发生，这样你就可以证明为什么你不处理它。

这题乍一看比较麻烦，但是只要获取了题目所给的关键信息：然后重复这个过程直到这个数变为1，也可能是无限循环，但始终变不到1。

也就是说，给定的数在循环（重复的这个过程）中只会有两种可能：

  • 最终结果为1，return true
  • 陷入无线循环，即过程中出现了重复的数字，return false

那么代码只要就只需要解决两个问题了：

  • 判断是否出现了重复的数字，直接使用set。

  • 获取一个数每一次将该数替换为它每个位置上的数字的平方和的数，我们定义一个getSun函数，代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    func getSum(n int) int {
       sum := 0
       for n > 0 {
          sum = sum + (n%10)*(n%10) // n最后一位进行平方
          n = n / 10                // n去除最后一位
       }
       return sum
    }

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func isHappy(n int) bool {
	set := make(map[int]struct{}, 0)
	for {
		if n == 1 {
			return true
		}
		n = getSum(n)
		if _, ok := set[n]; ok { // 出现了重复，说明陷入无限循环了
			return false
		}
		set[n] = struct{}{}
	}
}

func getSum(n int) int {
	sum := 0
	for n > 0 {
		sum = sum + (n%10)*(n%10) // n最后一位进行平方
		n = n / 10                // n去除最后一位
	}
	return sum
}

赎金信

代码随想录：

  • 赎金信

LeetCode 383. 赎金信

在哈希法中有一些场景就是为数组量身定做的。

数组

这种题没什么好说的了（这种思路在LeetCode 76. 最小覆盖子串的滑动窗口题解中，只是一个check函数）。

ransomNote 和 magazine 由小写英文字母组成，那么26长度的数组即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func canConstruct(ransomNote string, magazine string) bool {
	ransomArr, magazineArr := [26]int{}, [26]int{}
	for i := 0; i < len(ransomNote); i++ {
		ransomArr[ransomNote[i]-'a']++
	}
	for i := 0; i < len(magazine); i++ {
		magazineArr[magazine[i]-'a']++
	}
	for i := 0; i < 26; i++ {
		if ransomArr[i] > magazineArr[i] {
			return false
		}
	}
	return true
}

两数之和

代码随想录：

LeetCode 1. 两数之和

HashMap

具体实现不用多说了，之前写java的时候就实现过了。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
func twoSum(nums []int, target int) []int {
   res := make([]int, 0)
   m := make(map[int]int, 0) // key为nums[i]，value为i（即索引）
   for i, num := range nums {
      if value, ok := m[target-num]; ok {
         res = append(res, value, i)
         break
      }
      m[num] = i
   }
   return res
}

四数相加II

代码随想录：

LeetCode 454. 四数相加 II

HashMap

这题看起来比较麻烦，但其实总体思路是跟LeetCode 1. 两数之和一样的，使用HashMap来解决即可。

首先对这四个数组分一下组：nums1[i]+nums2[j]为一组，nums3[k]+nums4[l]为一组。在使用map时：key为nums1[i]+nums2[j]，value为这个值出现的次数。先通过一次双层循环得到map，再来一次双层循环来找到匹配到的结果。

思路很简单打一下草稿就能明白。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
	ans := 0
	mp := make(map[int]int, 0)
	n := len(nums1)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			mp[nums1[i]+nums2[j]]++
		}
	}
	for k := 0; k < n; k++ {
		for l := 0; l < n; l++ {
			//if _, ok := mp[0-(nums3[k]+nums4[l])]; ok { // 说明nums1[i]+nums2[j]+nums3[k]+nums4[l]==0，即我们想要的结果
			//	ans = ans + mp[0-(nums3[k]+nums4[l])]
			//}
			ans = ans + mp[0-(nums3[k]+nums4[l])] // 可以直接这样写，因为go中如果mp[key]中的key不存在，取出来的value是0
		}
	}
	return ans
}