哈希表 - 4. 四数相加 - 《算法》

解题思路
数组和对象实现
- 数组
- 对象
Map・循环不同
拓展
- 为什么本题 Map 比 Object 和 Array 快？
- 为什么本题 for 比 forEach 和 reduce 快？

本文我们一起用 3 种数据类型实现哈希表，实践 3 种循环直到更优解，并分析原因

解题思路

多数运算结果等于 指定值问题都可转为两数相加
超过两数就通过枚举固定多出数。本题转为 A B + C D = 0
即：C + D = 0 - A - B，枚举 A B 组合，以 0 - A - B 作键名存 A B组合数
枚举 C D 组合，C + D 在哈希表中，就找到 A B组合数种可能。累加即可

数组和对象实现

数组

var fourSumCount = function(A, B, C, D, t, h = [], r = 0) {
    for (var a of A) {
    }
      for (var b of B) h[t = 0 - a - b] = (h[t] || 0) + 1
    for (var c of C) for (var d of D) h[t = c + d] && (r += h[t])
    return r
};

对象

var fourSumCount = function(A, B, C, D, t, h = Object.create(null), r = 0) {
    for (var a of A) for (var b of B) h[t = 0 - a - b] = (h[t] || 0) + 1
    for (var c of C) for (var d of D) h[t = c + d] && (r += h[t])
    return r
};

Map・循环不同

reduce

var fourSumCount = function(A, B, C, D, t) {
    return C.reduce((h, c) => (D.forEach(d => h.has(t = c + d) && h.set('r', h.get('r') + h.get(t))), h) ,
           A.reduce((h, a) => (B.forEach(b => h.set(t = 0 - a - b, h.has(t) ? h.get(t) + 1: 1)), h), new Map([['r', 0]]))).get('r')
};

forEach

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number[]} nums3
 * @param {number[]} nums4
 * @return {number}
 */
var fourSumCount = function (A, B, C, D) {
  const map = new Map();
  let count = 0;
  A.forEach(a => {
    B.forEach(b => {
      const sum = a + b;
      map.set(sum, map.has(sum) ? map.get(sum) + 1 : 1);
    })
  })
  C.forEach(c => {
    D.forEach(d => {
      if (map.has(0 - c - d)) {
        count += map.get(0 - c - d);
      }
    })
  })
  return count;
};

for…of

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number[]} nums3
 * @param {number[]} nums4
 * @return {number}
 */
var fourSumCount = function(A, B, C, D) {
  let map = new Map()
  let count = 0
  // a+b 的所有组合
  for(let a of A){
    for(let b of B){
      const sum = a+b;
      map.set(sum, map.has(sum) ? map.get(sum)+1 : 1 );
    }
  }
  // 0-b-c 的所有组合
  for(let c of C){
    for(let d of D){
      if(map.has(0-c-d)) {
          count += map.get(0-c-d);
      }
    }
  }
  return result
};

for

var fourSumCount = function(A, B, C, D, t, h = new Map, r = 0) {
    for (var i = 0; i < A.length; i++) for (var j = 0; j < B.length; j++) h.set(t = 0 - A[i] - B[j], h.has(t) ? h.get(t) + 1 : 1)
    for (var i = 0; i < C.length; i++) for (var j = 0; j < D.length; j++) h.has(t = C[i] + D[j]) && (r += h.get(t))
    return r
};

拓展

为什么本题 Map 比 Object 和 Array 快？

1. Array 作哈希表

举例：4 个数组都是 [-227 , 227]，
Array 长度为 227 2，(0, 227 2) 间除了 227 都是 empty
负数索引，不影响数组长度，会变为对象属性，查找和 Object 一样

2. Object

可以解决键名不连续问题，又引入新问题：
查询或 for…in 遍历对象属性，会读取原型链上的属性
1. 可通过 Object.create(null) 创建无继承的对象
2. 或用 Object.hasOwnproperty(属性名) 代替对象.属性名判断属性是否存在
  3. Map
默认不包含任何键
提供 has 方法，与 get 复杂度相同，但无需区分 undefined 与假值。语义可读性更好
优化了频繁增删键值对的场景，在大量数据增删时，提升明显

4. 小结：

场景	适用数据结构
键名多连续，极小值极大值差小	优先数组
键名按小到大排序	优先数组或 Object
键名按插入顺序排序	优先 Map
频繁读取长度	优先数组，Map
频繁增删键值对	优先 Map

为什么本题 for 比 forEach 和 reduce 快？

1. forEach：

作为 ES5.1 高阶函数，对比循环控制语句
可传入 callback 回调函数，指定函数的 this
1. 每次迭代前，forEach 会检查下一项是否为empty，并将非empty 复制给 callback

var a = []
a[1] = 1, a[3] = 3
a.forEach(v => console.log(v)) // 输出1，3。第0项和第2项自动跳过。无需非空校验
for(var v of a) console.log(v) // ES5.1中，for也应检查empty后再赋值，但实际没有

  1. 以上为 forEach 带来方便的同时，也增加了性能开销

2. reduce：

作为 ES5.1 高阶函数，实现比 forEach 稍晚，通过累计器实现归并
可传入 callback 回调函数，指定累计器初始值

无初始值，非empty 的第 0 项为初始值，第 1 项为当前值，可减少1次迭代

[1,2].reudce((p, v) => p + v) // 使用reduce求累加和只用迭代1次
每次迭代前，reduce 会检查下一项是否为empty，并将非empty 复制给 callback

var a = []
a[1] = 1, a[3] = 3
a.reduce((p, v) => console.log(v)) // 输出3。第0项和第2项自动跳过。无需非空校验
用迭代前校验非empty 特性，循环中 splice(0) 或 length = 0 清空数组，实现终止循环

[1,2,3].forEach((v, , a)=>(console.log(v),a.splice(0))) // 输出1
[1,2,3].reduce((, v, i, a)=>(console.log(v),a.splice(0))) // 输出2
修改原数组有副作用。实践中请避免使用
抛出错误，可避免副作用终止循环

[1,2,3].forEach((, v, i, a)=>{console.log(v);throw ‘Error’}) // 输出1，抛出错误Error
[1,2,3].reduce((, v, i, a)=>{console.log(v);throw ‘Error’}) // 输出2，抛出错误Error
需提前终止循环的场景，Mozlia 建议使用 for 的 break

3. 综上

高阶函数在流程控制外，比 for 多做了其它开销性能的操作
仅循环场景中，循环次数越多，for 优势越明显
在实际项目中，遍历对象用 for 还是高阶函数呢？
在 Eslint 规则中，标准严于 Google 的《Airbnb JavaScript 风格指南》11.1 条建议

11.1 不要用遍历器。用 JavaScript 高级函数代替 for-in、 for-of。

不可变的规则：处理返回值的纯函数比副作用更容易
用数组的这些迭代方法： map () /every () /filter () /find () /findIndex () /reduce () /some () /… ,
用对象的这些方法 Object.keys () / Object.values () / Object.entries () 去产生一个数组，这样你就能去遍历对象了。

在较新的 Chrome86 中，100 * 100 次双重循环数组，累加操作。每秒操作数 QPS 如图
4. 四数相加 - 图1
测试代码：将原来的 console.log 改为累加操作，接近本题场景

// Setup
var a = Array.from({length:100}, (_, i) => i)
var b = Array.from({length:100}, (_, i) => i)
var r = 0
// for
for (var i = 0; i < a.length; i++) for (var j = 0; j < b.length; j++) r += a[i] + b[j]
// for...of
for (var i of a) for (var j of b) r += i + j
// for...in
for (var i in a) for (var j in b) r += a[i] + b[j]
// while
var i = -1
while(++i < a.length) {
    var j = - 1
    while(++j < a.length) r += a[i] + a[j]
}
// forEach
a.forEach(i => b.forEach(j => r += i + j))
// reduce
a.reduce((_, i) => b.reduce((_, j) => r += i + j))
while > for > for 语法糖 for...of > forEach 和 reduce > for...in

考虑性能，如短期使用，性能敏感的工具类应用或脚本，优先使用 for 和 while
考虑维护，如团队协作。在循环中有高级操作。优先使用 forEach 和 Reduce 等高阶函数
for…of 是兼顾可读性的中立选择
用 Object.keys() / Object.values() / Object.entries() 代替 for…in 遍历对象

4. 四数相加