454. 4Sum II M

 Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

 

Example 1:

Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Output: 2
Explanation:
The two tuples are:
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

Example 2:

Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1

 

Constraints:

• n == nums1.length
• n == nums2.length
• n == nums3.length
• n == nums4.length
• 1 <= n <= 200
• -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

A:

两两做map， 然后看其对应大负值是否存在。

class Solution {      // beat 5%
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        auto map1=helper(nums1,nums2);
        auto map2=helper(nums3,nums4);
        int res =0;
        for(const auto & p:map1){
            int key = p.first;
            int c1= p.second;
            auto it = map2.find(-key);
            res += (it != map2.end()? it->second * c1 : 0);
        }
        return res;
    }
private:
    map<int,int> helper(vector<int> & v1, vector<int>& v2){
        map<int,int> m;
        for(auto v : v1){
            for(auto k : v2){
                auto it = m.find(v+k);
                int value = it != m.end()? it->second : 0;
                m[v+k] = value +1;
            }
        }
        return m;
    }
};

注意到： C++ 里， map是ordered的，因此选择unordered_map. 

class Solution {      // beat 23%
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        auto map1=helper(nums1,nums2);
        auto map2=helper(nums3,nums4);
        int res =0;
        for(const auto & p:map1){
            int key = p.first;
            int c1= p.second;
            auto it = map2.find(-key);
            res += (it != map2.end()? it->second * c1 : 0);
        }
        return res;
    }
private:
    unordered_map<int,int> helper(vector<int> & v1, vector<int>& v2){
        unordered_map<int,int> m;
        for(auto v : v1){
            for(auto k : v2){
                auto it = m.find(v+k);
                int value = it != m.end()? it->second : 0;
                m[v+k] = value +1;
            }
        }
        return m;
    }
};

再次注意到，第二个map其实不需要保存，只需要build on the fly。 精简后的code

class Solution {  //beat 97%
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> m;
        for(auto v : nums1)
            for(auto k : nums2)
                ++m[v+k];
        
        int res = 0;
        for(auto a: nums3){
            for(auto b: nums4){
                auto it=m.find(0-a-b);
                if(it!= m.end()){
                    res += it->second;
                }
            }
        }
        return res;
    }
};

甚至， 利用语法糖， 不用去检查是否存在，直接利用不存在，检索为0的特性

it is actually safe to assume that the values inside Foo are always initialized to zero because of the behaviour of operator[]

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> m;
        for(auto v : nums1)
            for(auto k : nums2)
                ++m[v+k];
        
        int res = 0;
        for(auto a: nums3)
            for(auto b: nums4)
                res += m[0-a-b];
        return res;
    }
};