算法之四数之和Ⅱ - 翁先森的博客

454.四数字相加Ⅱ

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。

思路：

四个数之和咱们可以给他转换成2数之和，这里因为是4个数组，两两组合，之后用Map存储和值，因为既然要

使得 A[i] + B[j] + C[k] + D[l] = 0,换个思路就是使得 A[i] + B[j] = -C[k] - D[l]，AB一组遍历存键值，CD再去遍历找到键值相等的，那就是一组，或者多组，因为AB可能有多种情况，CD也是

1
/**
2
 * @param {number[]} A
3
 * @param {number[]} B
4
 * @param {number[]} C
5
 * @param {number[]} D
6
 * @return {number}
7
 */
8
var fourSumCount = function (A, B, C, D) {
9
    let h = new Map()
10
    let r = 0
11
    //遍历前两个参数，在map中以键值对方式添加所有可能的值
12
    //key值为-（a+b），当C D数组中的c+d=-（a+b）时候，说明组合起来会是0
13
    //key值存在的时候就+1，不存在就set为1
14
    for (var a of A) {
15
        for (var b of B) {
16
            if (h.get(0 - a - b)) {
17
                h.set(0 - a - b, h.get(0 - a - b) + 1)
18
            } else {
19
                h.set(0 - a - b, 1)
20
            }
21
        }
22
    }
23
    //C D中的值有匹配的话就在返回结果中加上key对应的value
24
    for (var c of C) {
25
        for (var d of D) {
26
            if (h.has(c + d)) {
27
                r += h.get(c + d)
28
            }
29
        }
30
    }
31
    return r
32
};