“This is the 18th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

describe

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] 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 = 0Copy the code

Note:

n == nums1.length
n == nums2.length
n == nums3.length
n == nums4.length
1 <= n <= 200
-2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28
Copy the code

parsing

Given four integer arrays A, B, C, and D of length N, return the number of tuples (I, j, k, l) such that:

  • 0 <= i, j, k, l < n
  • A[i] + B[j] + C[k] + D[l] == 0

But O(N^4) is not a very interesting time, because if you have a quadruple loop, the maximum possible time is O(10^8), In leetcode’s usual running conditions, so it’s bound to time out, O(1) space.

We can use A double for loop to store the sum of the elements of array A and array B into the dictionary T. Then we can use A double for loop to find the negative value of the sum of the elements of array C and array D in t. If it exists, result will be incresed by one. The result obtained at the end of traversal is the result, and the time complexity can also be reduced to O(N^2), and the space complexity is O(N).

answer

class Solution(object):
    def fourSumCount(self, A, B, C, D):
        """
        :type A: List[int]
        :type B: List[int]
        :type C: List[int]
        :type D: List[int]
        :rtype: int
        """
        result = 0
        for a in A:
            for b in B:
                for c in C:
                    for d in D:
                        if a+b+c+d == 0:
                            result += 1
        return result
Copy the code

The results

Time Limit Exceeded
Copy the code

answer

class Solution(object):
    def fourSumCount(self, A, B, C, D):
        """
        :type A: List[int]
        :type B: List[int]
        :type C: List[int]
        :type D: List[int]
        :rtype: int
        """
        t = {}
        for a in A:
            for b in B:
                t[a+b] = t.get(a+b,0)+1
        result = 0
        for c in C:
            for d in D:
                if -(c+d) in t:
                    result+=t[-(c+d)]
        return result
        	      
		
Copy the code

The results

Given in the linked list. Memory Usage: 10000 ms Submissions in the Python online submissions for 4Sum II.Copy the code

The original link

Leetcode.com/problems/4s…

Your support is my biggest motivation