454. 4Sum II

原题：454. 4Sum II

思路

这道题用dfs会超时，最终用分治 + 2-Sum的思想 解出。

source code

// Runtime: 736 ms, faster than 9.18% of JavaScript online submissions for 4Sum II.
// Memory Usage: 101.7 MB, less than 9.94% of JavaScript online submissions for 4Sum II.
var fourSumCount = function (A, B, C, D) {
  const helper = function (arr1, arr2) {
    const map = {};
    for (let num1 of arr1) {
      for (let num2 of arr2) {
        const sum = num1 + num2;
        map[sum] = (map[sum] || 0) + 1;
      }
    }

    return map;
  };

  const map1 = helper(A, B);
  const map2 = helper(C, D);
  let count = 0;
  for (let num1 in map1) {
    count += map1[num1] * (map2[-num1] || 0);
  }

  return count;
};

test cases

test("test1", () => {
  expect(fourSumCount([1, 2], [-2, -1], [-1, 2], [0, 2])).toEqual(2);
});

test("test2", () => {
  expect(fourSumCount([0, 0], [0, 0], [0, 0], [0, 0])).toEqual(16);
});

//这里还有一个超大的case，不赘述了。。