454-四数相加II
标签：数组 哈希表
题目信息
题目地址： 454. 四数相加 II
题目内容：
javascript
给你四个整数数组nums1、nums2、nums3和nums4，数组长度都是n
请你计算有多少个元组 (i, j, k, l)能满足：
1）0 <= i, j, k, l < n
2）nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
示例 1：
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
示例 2：
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1
提示：
n == nums1.length
n == nums2.length
n == nums3.length
n == nums4.length
1 <= n <= 200
-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228
题解
解法一
思路：
使用
哈希表思路来解决定义次数count = 0，定义一个map = new Map()
先遍历
nums1和nums2数组，将它们中各个元素相加的和存到map中，map中的key就是和，value就是这个和出现的次数然后遍历
nums3和nums4数组，算出要找的数字0 - (nums3[i] + nums4[j])，然后去map中是否有0 - (nums3[i] + nums4[j])这个key，如果找到，获取该key对应的value，然后将value累加到count中，最后返回count
代码实现：
javascript
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @param {number[]} nums3
* @param {number[]} nums4
* @return {number}
*/
var fourSumCount = function(nums1, nums2, nums3, nums4) {
// map的key就是当前的和，value就是当前和出现的次数
const sumMap = new Map()
let count = 0
for(let i = 0; i < nums1.length; i++) {
for(let j = 0; j < nums2.length; j++) {
const iValue = nums1[i] // 获取nums1当前项
const jValue = nums2[j] // 获取nums2当前项
const sum = iValue + jValue // 获取nums1当前项和nums2当前项的和sum
const mapValue = sumMap.get(sum) // 获取map中是否有sum
if(!!mapValue) { // 如果有 就将次数 + 1
sumMap.set(sum, mapValue + 1)
}else { // 如果没有 就将次数设置为 1
sumMap.set(sum, 1)
}
}
}
for(let p = 0; p < nums3.length; p++) {
for(let k = 0; k < nums4.length; k++) {
const pValue = nums3[p] // 获取nums3当前项
const kValue = nums4[k] // 获取nums4当前项
const difference = 0 - (pValue + kValue) // 获取要去map中找的数字
if(sumMap.has(difference)) {
count += sumMap.get(difference)
}
}
}
return count
};