###### tags: `Leetcode` `medium` `array` `hash` `python` `c++`

# 454. 4Sum II

## [題目連結:] https://leetcode.com/problems/4sum-ii/description/

## 題目:
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

## 解題想法:
* 此題為在四個數組中各取一個數字，使其和為0
* 若爆破法遍歷...time:O(n^4)
* 使用 [1. Two Sum](/9Oj4ypWESsCZdp4j3x_ssQ) 概念:
* AB、CD兩兩數組一組->簡化為TWO SUM問題
* time: O(n^2)
* 使用hash map存
* key: A、B數組之元素互相配對的不同總和
* value:組合數量
* 最後判斷C、D數組之元素互相配對取負號，是否出現於hash map中

## Python:

from collections import defaultdict
class Solution(object):
    def fourSumCount(self, nums1, nums2, nums3, nums4):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type nums3: List[int]
        :type nums4: List[int]
        :rtype: int
        """
        #AB CD兩兩一組->簡化為TWO SUM問題 O(n^2)
        dic=defaultdict(int) #key:總和 value:組合數量
        for i in nums1:
            for j in nums2:
                dic[i+j]+=1
        res=0
        for i in nums3:
            for j in nums4:
                if -(i+j) in dic:
                    res+=dic[-(i+j)]
        return res

nums1 = [1,2]
nums2 = [-2,-1]
nums3 = [-1,2]
nums4 = [0,2]

result=Solution()
ans=result.fourSumCount(nums1,nums2,nums3,nums4)
print(ans)

## C++:

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> dic;
        for (int i: nums1){
            for (int j: nums2)
                dic[i+j]+=1;
        }
        int res=0;
        for (int i: nums3){
            for (int j: nums4){
                if (dic.find(-(i+j))!=dic.end())
                    res+=dic[-(i+j)];
            }
        }
        return res;
    }
};