454 - 4Sum II

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

思路

本題解題步驟：

1. 首先定義 一個unordered_map，key放a和b兩數之和，value 放a和b兩數之和出現的次數。
2. 遍歷大A和大B數組，統計兩個數組元素之和，和出現的次數，放到map中。
3. 定義int變量count，用來統計 a+b+c+d = 0 出現的次數。
4. 在遍歷大C和大D數組，找到如果 0-(c+d) 在map中出現過的話，就用count把map中key對應的value也就是出現次數統計出來。
5. 最後返回統計值 count 就可以了

Solution

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        // nums1[i] + nums2[j] = - nums3[k] - nums4[l]
        // key放兩數之和, value放出現次數
        unordered_map <int, int> map;
        for ( int i = 0; i < nums1.size(); i++ ) {
            for ( int j = 0; j < nums2.size(); j++ ) {
                map[nums1[i]+nums2[j]]++;
            }
        }

        int count = 0;
        for ( int i = 0; i < nums3.size(); i++ ) {
            for ( int j = 0; j < nums4.size(); j++ ) {
                if ( map.find( 0 - nums3[i] - nums4[j]) != map.end() ) {
                    count += map[0 - nums3[i] - nums4[j]];
                }
            }
        }

        return count;
    }
};