0454. 4Sum II¶
题目信息¶
- 题号:
0454
- 难度:
Medium
- 主题:
四个等长数组、下标四元组、元素和为零、方案计数
- 原题:
- 重点:
分别从四个数组各选一个下标、相同数值的不同下标分别计数、只返回四元组数量
题目重述¶
给定四个长度均为 n 的整数数组 nums1、nums2、nums3、nums4,统计满足以下条件的下标四元组 (i, j, k, l) 数量:
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
每个下标分别取自对应数组,范围都是 [0, n-1]。n 位于 [1, 200],元素位于 [-2^28, 2^28],题目保证答案不超过 2^31-1。不同下标组合要分别计数,即使选中的数值完全相同。
自建示例¶
重复零值产生多个下标组合:
输入:nums1 = [1,-1]
nums2 = [-1,1]
nums3 = [0,0]
nums4 = [0,0]
输出:8
解释:前两个数组有两种下标配对使和为 0;后两个数组各有两个零,可形成 2×2 = 4 种下标组合,因此总数为 2×4 = 8。
没有零和四元组:
输入:nums1 = [1],nums2 = [1],nums3 = [1],nums4 = [1]
输出:0
解释:唯一四元组的元素和为 4,不满足条件。
把四元组拆成两组配对和¶
先枚举 nums1[i] + nums2[j],用哈希表记录每个和由多少个下标对产生;再枚举 nums3[k] + nums4[l],若其相反数为 need,就可以和前面的所有 -need 配对。频次而不是单个位置必须被保存,因为相同数值的不同下标组合都应计数。
数组元素可能接近 32 位边界,配对和使用 long long,避免求和在查表前溢出。
C++ 实现¶
class Solution {
public:
int fourSumCount(std::vector<int>& nums1,
std::vector<int>& nums2,
std::vector<int>& nums3,
std::vector<int>& nums4) {
std::unordered_map<long long, int> frequency;
for (int left : nums1) {
for (int right : nums2) {
++frequency[static_cast<long long>(left) + right];
}
}
long long answer = 0;
for (int left : nums3) {
for (int right : nums4) {
long long need =
-(static_cast<long long>(left) + right);
auto it = frequency.find(need);
if (it != frequency.end()) answer += it->second;
}
}
return static_cast<int>(answer);
}
};
代码分析¶
每个前半部分下标对只入表一次,后半部分下标对按需要查表一次;哈希频次会自动乘出相同数值对应的多种下标选择。两层枚举各处理 n^2 个组合,平均时间复杂度为 O(n^2),哈希表空间复杂度为 O(n^2)。