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:

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Example 1:

1
2
3
4
5
6
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:

1
2
Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1

题目大意

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

解题思路

采用哈希表分治的方法，将四数之和问题拆分为两数之和问题：

  1. 计算 nums1 和 nums2 中所有可能的两数之和，并将其出现次数存储在哈希表中。
  2. 计算 nums3 和 nums4 中所有可能的两数之和，然后查找哈希表中是否存在该和的相反数。
  3. 累计所有满足条件的组合数量。

这种方法将时间复杂度从 O (n⁴) 降低到 O (n²)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> sumCount;  // 存储nums1和nums2元素和的出现次数
        int count = 0;
        
        // 计算nums1和nums2所有可能的和及其出现次数
        for (int a : nums1) {
            for (int b : nums2) {
                sumCount[a + b]++;
            }
        }
        
        // 计算nums3和nums4所有可能的和，并查找是否存在相反数
        for (int c : nums3) {
            for (int d : nums4) {
                int target = -(c + d);
                // 如果存在对应的相反数，累加出现次数
                if (sumCount.find(target) != sumCount.end()) {
                    count += sumCount[target];
                }
            }
        }
        
        return count;
    }
};