LeetCode: 454 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 nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0.

Example:

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) => 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) => 2 + (-1) + (-1) + 0 = 0

问题

给定四个长度为 n 的整数数组 nums1、nums2、nums3 和 nums4，返回使得 nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 的元组 (i, j, k, l) 的数量。

解决方案 1

哈希表方法

Approach 1 / 方法 1

This solution uses a hash table to store the sum of pairs from nums1 and nums2 and then checks for complement sums from nums3 and nums4.

该解决方案使用哈希表存储 nums1 和 nums2 的对和，然后检查 nums3 和 nums4 的补充和。

Implementation / 实现

python

# Solution 1 implementation in Python
def fourSumCount(nums1, nums2, nums3, nums4):
    count = 0
    hashmap = {}

    # Store the sums of pairs from nums1 and nums2
    for a in nums1:
        for b in nums2:
            if a + b in hashmap:
                hashmap[a + b] += 1
            else:
                hashmap[a + b] = 1

    # Find the complement sums from nums3 and nums4
    for c in nums3:
        for d in nums4:
            target = -(c + d)
            if target in hashmap:
                count += hashmap[target]

    return count

Explanation / 解释

1. Step 1 / 第一步:

• Initialize a hash table hashmap to store sums of pairs from nums1 and nums2.
  初始化一个哈希表 hashmap 用于存储 nums1 和 nums2 的对和。

2. Step 2 / 第二步:

• Iterate through nums1 and nums2, compute their pair sums, and store them in the hash table.
  遍历 nums1 和 nums2，计算它们的对和，并将其存储在哈希表中。

3. Step 3 / 第三步:

• Initialize a counter count to keep track of valid tuples.
  初始化计数器 count 以跟踪有效的元组数量。

4. Step 4 / 第四步:

• Iterate through nums3 and nums4, compute their pair sums, and check if the complement sum exists in the hash table.
  遍历 nums3 和 nums4，计算它们的对和，并检查哈希表中是否存在补充和。

5. Step 5 / 第五步:

• If the complement sum exists, increment the counter by the value from the hash table.
  如果存在补充和，将计数器增加哈希表中的值。

Complexity Analysis / 复杂度分析

• Time Complexity: O(n^2), where n is the length of each array.
  时间复杂度: O(n^2)，其中n是每个数组的长度。

• Space Complexity: O(n^2), for storing the pair sums in the hash table.
  空间复杂度: O(n^2)，用于存储哈希表中的对和。

Key Concept / 关键概念

• Hash table to efficiently find complement sums for the four-array sum problem.
  使用哈希表高效找到四数组和问题的补充和。

解决方案 2

双哈希表方法

Approach 2 / 方法 2

This solution uses two hash tables, one for storing sums of pairs from nums1 and nums2, and another for storing sums of pairs from nums3 and nums4.

该解决方案使用两个哈希表，一个用于存储 nums1 和 nums2 的对和，另一个用于存储 nums3 和 nums4 的对和。

Implementation / 实现

python

# Solution 2 implementation in Python
def fourSumCount(nums1, nums2, nums3, nums4):
    count = 0
    hashmap1 = {}
    hashmap2 = {}

    # Store the sums of pairs from nums1 and nums2 in hashmap1
    for a in nums1:
        for b in nums2:
            if a + b in hashmap1:
                hashmap1[a + b] += 1
            else:
                hashmap1[a + b] = 1

    # Store the sums of pairs from nums3 and nums4 in hashmap2
    for c in nums3:
        for d in nums4:
            if c + d in hashmap2:
                hashmap2[c + d] += 1
            else:
                hashmap2[c + d] = 1

    # Find common sums in hashmap1 and hashmap2
    for sum1 in hashmap1:
        if -sum1 in hashmap2:
            count += hashmap1[sum1] * hashmap2[-sum1]

    return count

Explanation / 解释

1. Step 1 / 第一步:

• Initialize two hash tables hashmap1 and hashmap2 to store sums of pairs from nums1 & nums2, and nums3 & nums4 respectively.
  初始化两个哈希表 hashmap1 和 hashmap2 用于分别存储 nums1 和 nums2、nums3 和 nums4 的对和。

2. Step 2 / 第二步:

• Iterate through nums1 and nums2, compute their pair sums, and store them in hashmap1.
  遍历 nums1 和 nums2，计算它们的对和，并将其存储在 hashmap1 中。

3. Step 3 / 第三步:

• Iterate through nums3 and nums4, compute their pair sums, and store them in hashmap2.
  遍历 nums3 和 nums4，计算它们的对和，并将其存储在 hashmap2 中。

4. Step 4 / 第四步:

• Initialize a counter count to keep track of valid tuples.
  初始化计数器 count 以跟踪有效的元组数量。

5. Step 5 / 第五步:

• Iterate through hashmap1, and for each sum in hashmap1, check if the negative sum exists in hashmap2.
  遍历 hashmap1，对于 hashmap1 中的每个和，检查 hashmap2 中是否存在相反数。

6. Step 6 / 第六步:

• If the negative sum exists, increment the counter by the product of the values from both hash tables.
  如果存在相反数，将计数器增加两个哈希表中的值的乘积。

Complexity Analysis / 复杂度分析

• Time Complexity: O(n^2), where n is the length of each array.
  时间复杂度: O(n^2)，其中n是每个数组的长度。

• Space Complexity: O(n^2), for storing the pair sums in the hash tables.
  空间复杂度: O(n^2)，用于存储哈希表中的对和。

Key Concept / 关键概念

• Using two hash tables to efficiently find complement sums for the four-array sum problem.
  使用两个哈希表高效找到四数组和问题的补充和。

Comparison / 比较

Comparison Between All Approaches

1. Algorithm:

   • Approach 1 (Single Hash Table):

     • Uses one hash table to store sums of pairs from nums1 and nums2, and finds complements from nums3 and nums4.

   • Approach 2 (Double Hash Table):

     • Uses two hash tables, one for sums of pairs from nums1 & nums2, and another for sums from nums3 & nums4.

2. Efficiency:

   • Time Complexity:

     • Both approaches have a time complexity of O(n^2), where n is the length of each array.

   • Space Complexity:

     • Both approaches have a space complexity of O(n^2) for storing pair sums in hash tables.

3. Readability and Maintainability:

   • Approach 1 (Single Hash Table):
     • Simple and uses

   one hash table, making it easier to understand and implement.

   • Approach 2 (Double Hash Table):
     • Slightly more complex due to the use of two hash tables but can be more intuitive in separating pair sums.

4. Best Practice:

   • Recommended Solution: Approach 1 (Single Hash Table):
     • Reason: Approach 1 is preferred due to its simplicity and minimal use of data structures, making it easier to follow and maintain.

Summary / 总结

• Use Approach 1 for a simple and clear solution, ensuring readability and maintainability.
• Approach 1’s single hash table method is straightforward and effective.

Tips / 提示

• Hash tables are powerful tools for efficiently finding complement sums in multiple array problems.
• Ensure to handle edge cases such as empty arrays or no valid tuples.

Solution Template for similar questions / 提示

• Use hash table methods to efficiently store and find pair sums in multi-array problems.
• Implement multiple hash tables for clear separation of pair sums if needed.

What does the main algorithm of this question aim to test? / 这个问题的主要算法旨在测试什么？

Understanding of hash table techniques and their application in multi-array sum problems.

5 more similar questions / 推荐5问题

1. LeetCode 18. 4Sum
2. LeetCode 15. 3Sum
3. LeetCode 1. Two Sum
4. LeetCode 167. Two Sum II – Input array is sorted
5. LeetCode 16. 3Sum Closest