[LeetCode] 454. 4Sum II

https://leetcode.com/problems/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

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

Github Solution

#time: O(n^2), space: O(n^2)
class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        table_a = {}
        table_b = {}
        result = 0
        
        for num_first in nums1:
            for num_second in nums2:
                table_a[num_first+num_second] = table_a.get(num_first+num_second, 0) + 1
        
        for num_third in nums3:
            for num_fourth in nums4:
                table_b[num_third+num_fourth] = table_b.get(num_third+num_fourth, 0) + 1
                
        for sum_third_fourth, count in table_b.items():
            key = 0-sum_third_fourth
            result += table_a.get(key, 0)*count
        
        return result

sol:

1. using hash map
2. 先從前兩組數，找出所有相加的值及數量，存進hash map
3. 在從後兩組數，找出所有相加的值及數量，存進hash map
4. 遍歷後面的hash map裡所有的key值和對應的count，也就是後兩組數相加的值及數量。去看前兩組數有沒有可以跟此key相加為0的值，有的話去用值對應的數量，乘上count，加到result裡
5. 最後返回result