【JS】用哈希法得到四数相加元组数

思路

1. 根据题目这里是四个数组abcd的数相加，将数组两两分组，A大组为ab，B大组为cd
2. 由a+b+c+d=0可得A+B=0，即B=0-A
3. 遍历数组分别计算出AB大组所有sum值，先将A组sum值存进map里，再从map里面寻找有count个合适的B值（0-A），就可以得到元组数count。

步骤

1. 创建一个 Map：

   • 初始化一个空的 Map 对象 twoSumMap。

2. 构建两数之和的映射：

   • 遍历数组 nums1 和 nums2。
   • 对于每一对元素 (n1, n2)，计算它们的和 sum。
   • 在 twoSumMap 中更新这个和 sum 的计数。

3. 计算四数之和为0的组合数：

   • 遍历数组 nums3 和 nums4。
   • 对于每一对元素 (n3, n4)，计算它们的和 sum。
   • 检查 twoSumMap 中是否存在 0 - sum 的键，如果存在，则累加它的值到 count。

4. 返回结果：

   • 返回 count，即所有四数之和为0的组合数。

题目

示例代码

var fourSumCount = function(nums1, nums2, nums3, nums4) {
    // 创建一个 Map 对象来存储 nums1 和 nums2 中所有可能的和及其出现的次数
    const twoSumMap = new Map();
    // 初始化计数器，用于记录满足条件的四元组数量
    let count = 0;

    // 遍历 nums1 数组
    for (const n1 of nums1) {
        // 遍历 nums2 数组
        for (const n2 of nums2) {
            // 计算 nums1 和 nums2 当前元素的和
            const sum = n1 + n2;
            // 更新 twoSumMap，如果 sum 已存在，则增加其计数，否则设置为1
            twoSumMap.set(sum, (twoSumMap.get(sum) || 0) + 1);
        }
    }

    // 遍历 nums3 数组
    for (const n3 of nums3) {
        // 遍历 nums4 数组
        for (const n4 of nums4) {
            // 计算 nums3 和 nums4 当前元素的和
            const sum = n3 + n4;
            // 如果在 twoSumMap 中存在与当前和互为相反数的键，则将其计数加到 count 上
            // 0 - sum 表示我们寻找与 (n3 + n4) 和互为相反数的和
            count += (twoSumMap.get(0 - sum) || 0);
        }
    }

    // 返回满足条件的四元组数量
    return count;
};

---

欢迎指正！

原文地址：https://blog.csdn.net/m0_74662483/article/details/142798858

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！