1995. 统计特殊四元组

🟢   🔖  数组 哈希表 枚举  🔗 力扣 LeetCode

题目

Given a 0-indexed integer array nums, return the number of distinct quadruplets (a, b, c, d) such that:

• nums[a] + nums[b] + nums[c] == nums[d], and
• a < b < c < d

Example 1:

Input: nums = [1,2,3,6]

Output: 1

Explanation: The only quadruplet that satisfies the requirement is (0, 1, 2, 3) because 1 + 2 + 3 == 6.

Example 2:

Input: nums = [3,3,6,4,5]

Output: 0

Explanation: There are no such quadruplets in [3,3,6,4,5].

Example 3:

Input: nums = [1,1,1,3,5]

Output: 4

Explanation: The 4 quadruplets that satisfy the requirement are:

• (0, 1, 2, 3): 1 + 1 + 1 == 3
• (0, 1, 3, 4): 1 + 1 + 3 == 5
• (0, 2, 3, 4): 1 + 1 + 3 == 5
• (1, 2, 3, 4): 1 + 1 + 3 == 5

Constraints:

• 4 <= nums.length <= 50
• 1 <= nums[i] <= 100

题目大意

给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件的 不同 四元组 (a, b, c, d) 的 数目 ：

• nums[a] + nums[b] + nums[c] == nums[d] ，且
• a < b < c < d

示例 1：

输入： nums = [1,2,3,6]

输出： 1

解释： 满足要求的唯一一个四元组是 (0, 1, 2, 3) 因为 1 + 2 + 3 == 6 。

示例 2：

输入： nums = [3,3,6,4,5]

输出： 0

解释：[3,3,6,4,5] 中不存在满足要求的四元组。

示例 3：

输入： nums = [1,1,1,3,5]

输出： 4

解释： 满足要求的 4 个四元组如下：

• (0, 1, 2, 3): 1 + 1 + 1 == 3
• (0, 1, 3, 4): 1 + 1 + 3 == 5
• (0, 2, 3, 4): 1 + 1 + 3 == 5
• (1, 2, 3, 4): 1 + 1 + 3 == 5

提示：

• 4 <= nums.length <= 50
• 1 <= nums[i] <= 100

解题思路

本题目要求在数组中找到四个不同的索引 a, b, c, d，满足 nums[a] + nums[b] + nums[c] = nums[d]。我们通过优化暴力O(n^4) 的方法，使用 哈希表 优化为 O(n^2)，在大规模输入下表现更优。。

1. 初始化结果 res 为 0。

2. 转换为等式形式：

   • 重新整理条件为 nums[a] + nums[b] = nums[d] - nums[c]。

3. 倒序遍历：

   • 首先处理 c, d：计算 nums[d] - nums[c]，并将其存入哈希表 count 中，用于快速查询。
   • 再处理 a, b：对于每个 b，枚举所有 a，直接从哈希表中查找 nums[a] + nums[b] 的数量并累加到结果 res。

4. 动态更新哈希表：

   • 每次遍历到新的 b，将与 c, d 的可能差值 nums[d] - nums[c] 更新到哈希表中。

5. 最后返回结果 res。

复杂度分析

• 时间复杂度：O(n^2)，两层循环。
• 空间复杂度：O(n)，使用哈希表 count 存储 O(n) 个键值对。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var countQuadruplets = function (nums) {
	let res = 0; // 结果计数器
	const n = nums.length;

	let count = new Map(); // 哈希表记录 nums[d] - nums[c]
	count.set(nums[n - 1] - nums[n - 2], 1); // 初始化最后两个元素的差值

	// 从倒数第三个元素开始枚举 b
	for (let b = n - 3; b >= 1; b--) {
		// 枚举 a
		for (let a = b - 1; a >= 0; a--) {
			// 查找是否有匹配的 nums[a] + nums[b] 在哈希表中
			res += count.get(nums[a] + nums[b]) || 0;
		}

		// 更新哈希表：计算 nums[d] - nums[b] 并存入
		for (let d = n - 1; d > b; d--) {
			count.set(nums[d] - nums[b], (count.get(nums[d] - nums[b]) || 0) + 1);
		}
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
18	四数之和	[✓]	数组 双指针 排序	🟠	🀄️ 🔗
334	递增的三元子序列	[✓]	贪心 数组	🟠	🀄️ 🔗
1534	统计好三元组	[✓]	数组 枚举	🟢	🀄️ 🔗
2552	统计上升四元组		树状数组 数组 动态规划 2+	🔴	🀄️ 🔗