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)``。