力扣-哈希表-454 四数相加Ⅱ

思路

有了前几题的铺垫，容易想到应该使用哈希表判断是否（0 - 两数和）是否在一个两数和的哈希表中，由于数目之间分布很散，所以排除数组，可能有重复的使用了multiset，结果超时了

超时代码

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        vector<int> nums;
        multiset<int> set;
        
        for(int i = 0; i < nums3.size(); i++){
            for(int j = 0; j < nums4.size(); j++){
                set.insert(nums3[i] + nums4[j]);
            }
        }
        int result = 0;
        
        for(int i = 0; i < nums1.size(); i++){
            for(int j = 0; j < nums2.size(); j++){
                 result += set.count(0 - (nums1[i] + nums2[j]));
            }
        }

        return result;
    }
};

看完题解后发现，只需要把multiset更改为map即可，这样也可以完成计数

题解代码

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3,
                     vector<int>& nums4) {
        vector<int> nums;
        // multiset<int> set;
        unordered_map<int, int> umap;

        for (int i = 0; i < nums3.size(); i++) {
            for (int j = 0; j < nums4.size(); j++) {
                // set.insert(nums3[i] + nums4[j]);
                umap[nums3[i] + nums4[j]]++;
            }
        }
        int result = 0;
        for (int i = 0; i < nums1.size(); i++) {
            for (int j = 0; j < nums2.size(); j++) {
                //  result += set.count(0 - (nums1[i] + nums2[j]));
                if( umap.find(0 - (nums1[i] + nums2[j])) != umap.end() ){
                    result += umap[0 - (nums1[i] + nums2[j])];
                }
            }
        }

        return result;
    }
};