454. 四数相加 II

Problem: 454. 四数相加 II

思路

与有效字母异位次相似,一个set记录num1+num2的<值,次数>,遍历for c { for d }当 0 - (c + d) 在map中有key

复杂度

• 时间复杂度:

$O(n)$

• 空间复杂度:

$O(n)$

Code

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> ApB;
        int sum = 0;

        for(int a : nums1) {
            for(int b : nums2) {
                ApB[a+b]++;
            }
        }

        for(int c : nums3) {
            for(int d : nums4) {
                auto tar = ApB.find(0 - (c+d));
                if(tar != ApB.end()) {
                    sum += tar->second;                    
                }
            }
        }

        return sum;
    }
};