0454. 4Sum II

题目信息

题号:

0454

难度:

Medium

主题:

四个等长数组、下标四元组、元素和为零、方案计数

原题:

LeetCode 0454

重点:

分别从四个数组各选一个下标、相同数值的不同下标分别计数、只返回四元组数量

题目重述

给定四个长度均为 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)。