class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
}
};
454. 四数相加 II
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < nnums1[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.lengthn == nums2.lengthn == nums3.lengthn == nums4.length1 <= n <= 200-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228相似题目
原站题解
golang 解法, 执行用时: 112 ms, 内存消耗: 6.5 MB, 提交时间: 2022-11-29 11:13:20
func fourSumCount(a, b, c, d []int) (ans int) {
countAB := map[int]int{}
for _, v := range a {
for _, w := range b {
countAB[v+w]++
}
}
for _, v := range c {
for _, w := range d {
ans += countAB[-v-w]
}
}
return
}
javascript 解法, 执行用时: 200 ms, 内存消耗: 44.9 MB, 提交时间: 2022-11-29 11:12:45
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @param {number[]} nums3
* @param {number[]} nums4
* @return {number}
*/
var fourSumCount = function(A, B, C, D) {
const countAB = new Map();
A.forEach(u => B.forEach(v => countAB.set(u + v, (countAB.get(u + v) || 0) + 1)));
let ans = 0;
for (let u of C) {
for (let v of D) {
if (countAB.has(-u - v)) {
ans += countAB.get(-u - v);
}
}
}
return ans;
};
python3 解法, 执行用时: 556 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-29 11:12:08
class Solution:
def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
countAB = collections.Counter(u + v for u in A for v in B)
ans = 0
for u in C:
for v in D:
if -u - v in countAB:
ans += countAB[-u - v]
return ans