day27【LeetCode】454. 四数相加 II

本文主要是介绍day27【LeetCode】454. 四数相加 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

day27【LeetCode】454. 四数相加 II

1.题目描述

附上题目链接：四数相加 II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
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

2.题解

`c++`

（写法一）

class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int,int> mymap;int count=0;for(int a : nums1){for(int b : nums2){mymap[a+b]++;}}for(int c:nums3){for(int d:nums4){if(mymap.find(0-(c+d)) != mymap.end()){count += mymap[0-(c+d)];}}}return count;}
};

解读：

定义了一个 unordered_map<int, int> 类型的哈希表 mymap，用于存储两个数组中元素的和以及对应的出现次数。
遍历 nums1 和 nums2 两个数组，将两个数组中元素两两相加的结果存入哈希表 mymap 中。
再次遍历 nums3 和 nums4 两个数组，在遍历过程中，判断哈希表中是否存在 -(c+d) 这个值，若存在，则将对应的数量累加到 count 中。
最终返回 count，即满足条件的两两相加等于 0 的组合数量。

（写法二）

public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int,int> mymap;int count=0;for(int a : nums1){for(int b : nums2){mymap[a+b]++;}}for(int c:nums3){for(int d:nums4){if(mymap.count(-c-d)){count += mymap[-c-d];}}}return count;}
};

本质是一样的，只不过在寻找对应数的时候，用的是count函数以及简化了写法。

`python`

(版本一)使用字典

class Solution:def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:mymap = dict()count = 0for a in nums1:for b in nums2:if a+b in mymap:mymap[a+b] += 1else:mymap[a+b] = 1for c in nums3:for d in nums4:if -c-d in mymap:count += mymap[-c-d]return count

第一个if那儿，可以换成下面这种写法，一行搞定。

mymap[a+b] = mymap.get(a+b, 0) + 1

(版本二)使用defaultdict

class Solution:def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:rec = defaultdict(int)count = 0for i in nums1:for j in nums2:rec[i+j] += 1for i in nums3:for j in nums4:count += rec.get((-i-j),0)return count

(版本三)使用counter

class Solution:def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:rec = collections.Counter(i+j for i in nums1 for j in nums2)count = 0for i in nums3:for j in nums4:if -i-j in rec:count += rec[-i-j]return count