888. 公平的糖果棒交换

题目

爱丽丝和鲍勃有不同大小的糖果棒：A[i] 是爱丽丝拥有的第 i 根糖果棒的大小，B[j] 是鲍勃拥有的第 j 根糖果棒的大小。

因为他们是朋友，所以他们想交换一根糖果棒，这样交换后，他们都有相同的糖果总量。

返回一个整数数组 ans，其中 ans[0] 是爱丽丝必须交换的糖果棒的大小，ans[1]  是 Bob 必须交换的糖果棒的大小。

如果有多个答案，你可以返回其中任何一个。保证答案存在。

例

输入：A = [1,1], B = [2,2]

输出：[1,2]

题解

哈希表

记 爱丽丝的棒棒总数为 sum_a 鲍勃的总数为 sum_b

爱丽丝和鲍勃交换的分别为 a b

如果交换后相等可以得到 sum_a - a + b = sum_b - b + a

转换可得 sum_a + 2b = sum_b + 2a => a = (sum_a - sum_b)/2 + b

/**
 * @param {number[]} A
 * @param {number[]} B
 * @return {number[]}
 */
var fairCandySwap = function(A, B) {
  // 计算 A B 总数
  let sum_a = A.reduce((pre, total) => (total += pre));
  let sum_b = B.reduce((pre, total) => (total += pre));

  // 建立 A 的哈希表
  let ma = new Set(A);

  let x = (sum_a - sum_b) / 2;

  // 遍历 b 计算对应的 a 的值，如果存在即为结果
  for (let b of B) {
    let a = b + x;
    if (ma.has(a)) {
      return [a, b];
    }
  }
};

时间复杂度：O(n+m) 空间复杂度：O(n) 其中 n 为建立哈希表 A 的长度