454. 四数相加 II

🟠   🔖  数组 哈希表  🔗 力扣 LeetCode

题目

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]

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.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

题目大意

给你四个整数数组 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) 的时间复杂度，效率极低。

为了解决这个问题，可以使用 哈希表 + 两两分组 进行优化，将时间复杂度降为 O(n²)。

1. 两两分组，减少计算量

   • 先计算 nums1 + nums2 的所有 两数之和，并使用 哈希表 map 记录每个和的出现次数。
   • 这样，我们就把 原本的四个数组变成了两个数组的计算问题，从 O(n^4) 降到 O(n^2)。

2. 查找匹配的和

   • 计算 nums3 + nums4 的所有两数之和，并 查找 map 是否存在与之相加为 0 的数。
   • 也就是说，我们在遍历 nums3 和 nums4 时，计算 -(nums3[k] + nums4[l])，然后看 map 里是否有这个值：
     • 如果 map 里有该值，说明 nums1 + nums2 里有这么多种方式可以与 nums3 + nums4 配对，使总和为 0。

3. 更新组合计数

   • 累加 map 中的次数到满足条件的组合计数中。
   • 循环结束后，返回组合计数。

复杂度分析

• 时间复杂度： O(n^2)

  • 计算 nums1 + nums2 所有组合：O(n^2)
  • 计算 nums3 + nums4 并查找 map：O(n^2)
  • 总体 O(n^2 + n^2) = O(n^2)

• 空间复杂度： O(n^2)，map 最多存储 n^2 个不同的和。

代码

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number[]} nums3
 * @param {number[]} nums4
 * @return {number}
 */
var fourSumCount = function (nums1, nums2, nums3, nums4) {
	const map = new Map();
	let res = 0;

	// 计算 nums1 + nums2 的所有和，存入哈希表
	for (let a of nums1) {
		for (let b of nums2) {
			const sum = a + b;
			map.set(sum, (map.get(sum) || 0) + 1);
		}
	}

	// 计算 nums3 + nums4 的所有和，查找 `map` 中的 `-sum`
	for (let c of nums3) {
		for (let d of nums4) {
			const sum = -(c + d);
			if (map.has(sum)) {
				res += map.get(sum); // 累加匹配的个数
			}
		}
	}

	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
18	四数之和	[✓]	数组 双指针 排序	🟠	🀄️ 🔗