四数相加 II--力扣454
四数相加 II
- 题目
- 思路
- C++代码
题目
思路
我们需要统计元组的个数,并且不需要排序和去重,所以选择哈希表unordered_map。
要使得a+b+c+d=0,我们首先利用map在前两个数组中统计a+b的值以及该值出现的次数。
接下来我们去后两个数组中查找0-(c+d),因为a+b=0-(c+d),如果能够找到,说明在这四个数组中存在a+b+c+d=0,那么上述统计的a+b出现的次数即为元组个数,我们用count累计一下,然后继续遍历。
C++代码
class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int, int> map;//出现的元组个数int count = 0;//统计前两个数组元素之和a+b,以及出现的次数。for (int a : nums1) {for (int b : nums2) {map[a + b]++;}}//接下来在另外两个数组找到0-(a+b),上面统计的次数就为满足题目要求的元组数for (int c : nums3) {for (int d : nums4) {if (map.find(0 - (c + d)) != map.end()) {count += map[0 - (c + d)];}}}return count;}
};