Medium

题目描述

给你四个整数数组 nums1、nums2、nums3 和 nums4，数组长度都是 n，请你计算有多少个元组 (i, j, k, l) 能满足：

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

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：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 = 0

示例 2：

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

提示：

  • 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

解题思路

这是一道经典的哈希表优化问题。暴力解法需要四层嵌套循环，时间复杂度为 O(n^4)，显然会超时。

核心思路：分组 + 哈希表

我们可以将四个数组分成两组：

  • 第一组：nums1 和 nums2
  • 第二组：nums3 和 nums4

算法步骤：

  1. 遍历 nums1 和 nums2，计算所有可能的两数之和，用哈希表记录每个和值出现的次数
  2. 遍历 nums3 和 nums4，计算所有可能的两数之和，然后在哈希表中查找是否存在对应的负值
  3. 如果存在，说明找到了四数之和为 0 的组合，将对应的次数累加到结果中

为什么这样做有效？

  • 如果 nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
  • 那么 nums1[i] + nums2[j] == -(nums3[k] + nums4[l])
  • 这样我们就将四数问题转化为了两个两数问题

这种分组策略将时间复杂度从 O(n^4) 优化到了 O(n^2)，是一个非常经典的优化技巧。

代码实现

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> map;
        
        // 统计 nums1 和 nums2 中所有两数之和的出现次数
        for (int num1 : nums1) {
            for (int num2 : nums2) {
                map[num1 + num2]++;
            }
        }
        
        int count = 0;
        // 遍历 nums3 和 nums4，查找对应的负值
        for (int num3 : nums3) {
            for (int num4 : nums4) {
                int target = -(num3 + num4);
                if (map.count(target)) {
                    count += map[target];
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        from collections import defaultdict
        
        # 统计 nums1 和 nums2 中所有两数之和的出现次数
        sum_map = defaultdict(int)
        for num1 in nums1:
            for num2 in nums2:
                sum_map[num1 + num2] += 1
        
        count = 0
        # 遍历 nums3 和 nums4，查找对应的负值
        for num3 in nums3:
            for num4 in nums4:
                target = -(num3 + num4)
                count += sum_map[target]
        
        return count

public class Solution {
    public int FourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        var map = new Dictionary<int, int>();
        
        // 统计 nums1 和 nums2 中所有两数之和的出现次数
        foreach (int num1 in nums1) {
            foreach (int num2 in nums2) {
                int sum = num1 + num2;
                if (map.ContainsKey(sum)) {
                    map[sum]++;
                } else {
                    map[sum] = 1;
                }
            }
        }
        
        int count = 0;
        // 遍历 nums3 和 nums4，查找对应的负值
        foreach (int num3 in nums3) {
            foreach (int num4 in nums4) {
                int target = -(num3 + num4);
                if (map.ContainsKey(target)) {
                    count += map[target];
                }
            }
        }
        
        return count;
    }
}

var fourSumCount = function(nums1, nums2, nums3, nums4) {
    const map = new Map();
    
    // 统计 nums1 和 nums2 中所有两数之和的出现次数
    for (const num1 of nums1) {
        for (const num2 of nums2) {
            const sum = num1 + num2;
            map.set(sum, (map.get(sum) || 0) + 1);
        }
    }
    
    let count = 0;
    // 遍历 nums3 和 nums4，查找对应的负值
    for (const num3 of nums3) {
        for (const num4 of nums4) {
            const target = -(num3 + num4);
            if (map.has(target)) {
                count += map.get(target);
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)需要遍历两次 n² 的组合
空间复杂度O(n²)哈希表最多存储 n² 个不同的和值

相关题目