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 < nnums1[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
Constraints:
n == nums1.lengthn == nums2.lengthn == nums3.lengthn == nums4.length1 <= n <= 200-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228
The description was taken from https://leetcode.com/problems/4sum-ii.
#O(N^2) Time, O(N) Space
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
counts = {}
output = 0
for num_one in nums1:
for num_two in nums2:
pair = num_one + num_two
if pair not in counts:
counts[pair] = 1
else:
counts[pair] += 1
for num_one in nums3:
for num_two in nums4:
complement = 0 - (num_one + num_two)
if complement in counts:
output += counts[complement]
return outputIn this question, we are looking at pairs of numbers that can sum to a specific value, zero.
Since we aren't considering the values themselves and only the sum, that means we are looking for two, two-sums that sum to zero.
When we see a requirement like this, similar to problems like Pairs of Songs With Total Durations Divisible by 60, a HashMap is a good approach.
Similar to the Two-Sum problem, we will utilize the x+y=z algorithm, solving for y, which becomes y=z-x, y is the current pair's complement from the first two arrays, x is the current pair from the second two arrays, and z is zero, the target.
We will pair each sum from the first two arrays and store them in a hashmap, then we will iterate through the second two arrays, and see if the complement, the target subtracted by the current sum, is in the hashmap.
If it is, we will increment the count by the frequency of pairs we have in the hashmap for that sum, since there could be multiple.
Let's start by creating our counts hashmap and our output counter.
counts = {}
output = 0
Then, we will iterate through the first two arrays to get each combination of pair sums.
for num_one in nums1:
for num_two in nums2:
pair = num_one + num_two
For each pair sum combination, if it is not in the hashmap, we will put it there.
If it is, we will increment the frequency of that pair sum.
if pair not in counts:
counts[pair] = 1
else:
counts[pair] += 1
Then, we will iterate through the second two lists to get each pair sum combination.
for num_one in nums3:
for num_two in nums4:
In order to sum to zero, we will need to subtract the current pair sum by zero to see which pair sum we need to equal zero, that is our current complement.
complement = 0 - (num_one + num_two)
If that complement is in the hashmap, we will increment the output by however many times it is in there. The reasoning for this is if we have four pairs of negative two in the hashmap, and our current pair sum is a two, then we just found four four-sums that sum to zero.
if complement in counts:
output += counts[complement]
Once we have calculated each pair-sum from the second two arrays and found how many four-sums we have, we will return that output.
return output