哈希表是根据关键码的值而直接进行访问的数据结构。其实直白来讲其实数组就是一张哈希表。

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法

数值的范围小，可用数组充当哈希表

当明确知道需要定义一个不是很大的集合时，可以直接用数组充当哈希表，不必使用std::unordered_set等。

有效的字母异位词

Leetcode：242.有效的字母异位词

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

示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true

示例 2: 输入: s = “rat”, t = “car” 输出: false

说明: 你可以假设字符串只包含小写字母

思路：由于给定的字符串是小写英文字母，总共有26个，所以定义一个26大小的数组即可，然后把字符减去’a’，把字母映射到数组中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func isAnagram(s string, t string) bool {
    record  := [26]int{}
    for _, r := range s {
        record[r - rune('a')]++
    }
    for _, r := range t {
        record[r - rune('a')]--
    }

    for i := 0; i < len(record); i++ {
        if record[i] != 0 {
            return false
        }
    }
    return record == [26]int{}    // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
}

数值的范围大，用真正的哈希表set

使用数组来做哈希的题目，是因为题目都限制了数值的大小，而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了

两个数组的交集

Leetcode：349.两个数组的交集

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

示例 1：

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

示例 2：

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

思路分析：使用哈希表解决数值范围大的问题，C++中可以使用unordered_set，底层是哈希表，读写效率最高，并且不需要排序；而go使用map[int]struct{}替代哈希表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func intersection(nums1 []int, nums2 []int) []int {
    set := make(map[int]struct{}, 0)

    res := make([]int, 0)

    for _, v := range nums1 {
        set[v] = struct{}{}
    }

    for _, v := range nums2 {
        if _, ok := set[v]; ok {
            res = append(res, v)
            delete(set, v)   // 返回结果不能重复，所以需要删掉
        }
    }

    return res
}

快乐数

Leetcode：202.快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。

然后重复这个过程直到这个数变为 1，也可能是 *无限循环* 但始终变不到 1。

如果 *可以变为* 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 true ；不是，则返回 false 。

*示例 1：*

****输入：****19

****输出：****true

*解释：*

1^2 + 9^2 = 82

8^2 + 2^2 = 68

6^2 + 8^2 = 100

1^2 + 0^2 + 0^2 =

思路：题目中说了会无限循环，那么也就是说求和的过程中，sum重复出现，就不是快乐数，当sum等于1时，就是快乐数！当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。所以此题就是把sum值存在哈希表里，然后每次循环查询哈希表里是否有这个值，和判断sum值是否等于1。

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
26
27
28
func isHappy(n int) bool {
	set := make(map[int]struct{}, 0)

	for {
		sum := getSum(n)
		if sum == 1 {
			return true
		}

		if _, ok := set[sum]; ok {  // 判断数是否出现过
			return false
		} else {
			set[sum] = struct{}{}
		}
		n = sum // 执行新的数
	}
}

func getSum(n int) int {
	sum := 0

	for n > 0 {
		sum += (n % 10) * (n % 10)
		n /= 10
	}

	return sum
}
  • 时间复杂度: O(logn)
  • 空间复杂度: O(logn)

数值的范围大，用真正的哈希表map

两数之和

Leetcode：两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

思路：哈希表key代表值，value代表下标，在哈希表中查找key为target-nums[i]的值，找到了，就直接返回两个的下标，找不到则插入哈希表里。

1
2
3
4
5
6
7
8
9
10
11
12
func twoSum(nums []int, target int) []int {
    m := make(map[int]int, 0)   // key是值，value存值在nums中所在的下标

    for k, v := range nums {
        if index, ok := m[target - v]; ok {	// 重点：target - v
            return []int{k, index}
        }
        m[v] = k
    }

    return []int{}
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)