哈希表（二）

454.四数相加 II

参考：代码随想录454.四数相加

思路

题目中给出了四个长度相同数组，并且要求求出组成结果为0的四元组。答案可以包含重复的四元组。

1. 先使用哈希表 key存储数组1和数组2的2个数之和，value存储数组1和数组2的2个数之和出现的次数
2. 遍历数组3和数组4在哈希表中找到key为-(num3+num4)，如果可以在哈希表中找到，那么就在返回结果上加上value次。

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
	m := map[int]int{}
	for _, num1 := range nums1 {
		for _, num2 := range nums2 {
			m[num1+num2]++
		}
	}
	rlt := 0
	for _, num3 := range nums3 {
		for _, num4 := range nums4 {
			rlt += m[-num3-num4]
		}
	}

	return rlt
}

本题总结

很容易的一道题，使用哈希表可以显著的降低时间复杂度。

383.赎金信

参考：代码随想录383.赎金信

看完题目的第一想法

题目判断第一个字符串ransomNote能否由magazine构成。而且组成的字符只能使用一次。

func canConstruct(ransomNote string, magazine string) bool {
	m := make(map[rune]int)
	for _, ch := range magazine {
		m[ch]++
	}

	for _, ch := range ransomNote {
		m[ch]--
		if v, ok := m[ch]; ok && v < 0 {
			return false
		}
	}

	return true
}

优化

func canConstruct(ransomNote string, magazine string) bool {
	record := [26]int{}
	for _, ch := range magazine {
		record[ch-'a']++
	}

	for _, ch := range ransomNote {
		record[ch-'a']--
		if record[ch-'a'] < 0 {
			return false
		}
	}

	return true
}

本题总结

与242.有效的字母异位词类似的一道题，做起来没有什么难度。可以使用数组代替哈希表。

未完待续。。