当前位置：首页 > article >正文

四数相加 II--力扣454

article 2025/3/12 20:28:16

四数相加 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;
    }
};