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