4 sum II

'''
For any valid quadruple (i, j, k, l), we must have:
nums1[i] + nums2[j] + nums3[k] + nums4[l] = 0

This can be rearranged as:
(nums1[i] + nums2[j]) = -(nums3[k] + nums4[l])

First, we compute all possible sums of nums1 and nums2 and store their frequencies in a hashmap.
Then, for each sum of nums3 and nums4, we check if its negative exists in the hashmap.
If it exists, we add its frequency to the answer.

This counts all valid quadruples efficiently in O(n^2) time.
'''

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        dict1={}
        for i in range(len(nums1)):
            for j in range(len(nums2)):
                cur=nums1[i]+nums2[j]
                dict1[cur]=dict1.get(cur,0)+1

        print(dict1)
        ans=0
        for i in range(len(nums3)):
            for j in range(len(nums4)):
                cur=nums3[i]+nums4[j]
                if 0-cur in dict1:
                    ans+=dict1[0-cur]
        return ans