LC 0454 [M] 4Sum II - ALawliet/algorithms GitHub Wiki
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
n = len(nums1)
sum_to_freq = defaultdict(int) # sum => freq
count = 0
# O(n^2): precompute pos 2sums
for i in range(n):
for j in range(n):
pos_2sum = nums1[i] + nums2[j]
sum_to_freq[pos_2sum] += 1
for k in range(n):
for l in range(n):
neg_2sum = 0 - (nums3[k] + nums4[l])
count += sum_to_freq[neg_2sum]
return count