day6 | 哈希表 part-2 | 454 四数相加II 、383. 赎金信、15. 三数之和、18. 四数之和
今日任务
- 454 四数相加II (题目: . - 力扣（LeetCode）)
- 383 赎金信 （题目: . - 力扣（LeetCode））
454 四数相加II
题目：. - 力扣（LeetCode）
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
想法:
无思路，四个数的累加，一开始想着暴力，暴力都要写好多层啊
题解:
这道题目是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以相对于题目18. 四数之和，题目15.三数之和，还是简单了不少！
解决思路:
- 首先定义 一个map，key放a和b两数之和，value 放a和b两数之和出现的次数。
- 遍历nums1和 nums2 数组，统计两个数组元素之和，和出现的次数，放到map中。
- 定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
- 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
- 最后返回统计值 count 就可以了
// 哈希法，利用一个map key用来记录前两个值，值记录出现的次数。
// 这里前提没有要求不能有重复的元组，而且4个数组的长度一样长
func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {m := make(map[int]int)var result intfor _, v1 := range nums1 {for _, v2 := range nums2 {m[v1+v2]++}}
// 遍历nums3和nums4数组，找到如果 0-(v3+v4) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来for _, v3 := range nums3 {for _, v4 := range nums4 {if _, ok := m[-v3-v4]; ok {result += m[-v3-v4]}}}return result
}
383 赎金信
题目：. - 力扣（LeetCode）
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
想法:
暴力可解，还和昨天的题目 “242.有效的字母异位词 ” 很像
题解:
题解和思路参考了：代码随想录
解决思路:
这道题目和242.有效的字母异位词 很像，相当于求 字符串a 和 字符串b 是否可以相互组成 ，而这道题目是求 字符串a能否组成字符串b，而不用管字符串b 能不能组成字符串a。
本题判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成，但是这里需要注意两点。
-
第一点“为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思” 这里说明杂志里面的字母不可重复使用。
-
第二点 “你可以假设两个字符串均只含有小写字母。” 说明只有小写字母，这一点很重要
func canConstruct(ransomNote string, magazine string) bool {record := make([]int, 26)for _, v := range magazine { // 通过record数据记录 magazine里各个字符出现次数record[v-'a']++}for _, v := range ransomNote { // 遍历ransomNote，在record里对应的字符个数做--操作record[v-'a']--if record[v-'a'] < 0 { // 如果小于零说明ransomNote里出现的字符，magazine没有return false}}return true
}15. 三数之和、18. 四数之和
这两道题对我来说很难，题解和思路待我研究明白后补齐。。。嘻嘻