算法(20)-四数相加II

哈希表

 2024/03/12 

题目(medium)

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

思路

const fourSumCount = (nums1, nums2, nums3, nums4) => {
    const twoSumMap = new Map();
    let count = 0;
    for(const n1 of nums1) {
        for(const n2 of nums2) {
            const sum = n1 + n2;
            twoSumMap.set(sum, (twoSumMap.get(sum) || 0) + 1);
        }
    }
    for(const n3 of nums3) {
        for(const n4 of nums4) {
            const sum = n3 + n4;
            count += (twoSumMap.get(0 - sum) || 0);
        }
    }
    return count;
}

原文作者：Yizhou Shen

原文链接：http://shenyizhou.github.io/2024/03/12/2024-03-12-%E7%AE%97%E6%B3%95(20)-%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II/

发表日期：March 12th 2024, 3:52:53 pm

更新日期：March 17th 2024, 4:12:55 pm

Next Post

算法(21)-赎金信
Previous Post

算法(19)-两数之和

CATALOG

1. 题目(medium)
2. 思路