目录
统计特殊四元组
描述
示例 1
示例 2
示例 3
提示
方法一：暴力
方法二：哈希表
方法三：哈希改进
统计特殊四元组
描述
给你一个下标从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
方法一：暴力
class Solution {
public int countQuadruplets(int[] nums) {
int n = nums.length;
int ans = 0;
for (int a = 0; a < n; ++a) {
for (int b = a + 1; b < n; ++b) {
for (int c = b + 1; c < n; ++c) {
for (int d = c + 1; d < n; ++d) {
if (nums[a] + nums[b] + nums[c] == nums[d]) {
++ans;
}
}
}
}
}
return ans;
}
}
方法二：哈希表
如果我们已经枚举了前三个下标 a,b,c，那么就已经知道了等式左侧 nums[a]+nums[b]+nums[c] 的值，即为 nums[d] 的值。对于下标 d 而言，它的取值范围是 c < d < n，那么我们可以使用哈希表统计数组 nums[c+1] 到 nums[n−1] 中每个元素出现的次数。这样一来，我们就可以直接从哈希表中获得满足等式的 d 的个数，而不需要在 [c+1,n−1] 的范围内进行枚举了。
在枚举前三个下标 a,b,c 时，我们可以先逆序枚举 c。在 c 减小的过程中，d 的取值范围是逐渐增大的：即从 c+1 减小到 c 时，d 的取值范围中多了 c+1 这一项，而其余的项不变。因此我们只需要将 nums[c+1] 加入哈希表即可。
在这之后，我们就可以枚举 a,b 并使用哈希表计算答案了。
class Solution {
public int countQuadruplets(int[] nums) {
int n = nums.length;
int ans = 0;
Map cnt = new HashMap();
for (int c = n - 2; c >= 2; --c) {
cnt.put(nums[c + 1], cnt.getOrDefault(nums[c + 1], 0) + 1);
for (int a = 0; a < c; ++a) {
for (int b = a + 1; b < c; ++b) {
ans += cnt.getOrDefault(nums[a] + nums[b] + nums[c], 0);
}
}
}
return ans;
}
}
方法三：哈希改进
我们将等式左侧的 nums[c] 移动到右侧，变为：
如果我们已经枚举了前两个下标 a,b，那么就已经知道了等式左侧 nums[a]+nums[b] 的值，即为 nums[d]−nums[c] 的值。对于下标 c,d 而言，它的取值范围是 b < c < d < n，那么我们可以使用哈希表统计满足上述要求的每一种 nums[d]−nums[c] 出现的次数。这样一来，我们就可以直接从哈希表中获得满足等式的 c,d 的个数，而不需要在 [b+1,n−1] 的范围内进行枚举了。
在枚举前两个下标 a,b 时，我们可以先逆序枚举 b。在 b 减小的过程中，c 的取值范围是逐渐增大的：即从 b+1 减小到 b 时，c 的取值范围中多了 b+1 这一项，而其余的项不变。因此我们只需要将所有满足 c=b+1 且 d>c 的 c,d 对应的 nums[d]−nums[c] 加入哈希表即可。
在这之后，我们就可以枚举 aa 并使用哈希表计算答案了。
class Solution {
public int countQuadruplets(int[] nums) {
int n = nums.length;
int ans = 0;
Map cnt = new HashMap();
for (int b = n - 3; b >= 1; --b) {
for (int d = b + 2; d < n; ++d) {
cnt.put(nums[d] - nums[b + 1], cnt.getOrDefault(nums[d] - nums[b + 1], 0) + 1);
}
for (int a = 0; a < b; ++a) {
ans += cnt.getOrDefault(nums[a] + nums[b], 0);
}
}
return ans;
}
}
