javascript - 找到总和为目标值的所有对

Question

我一直在查看这个示例，据称这是一种比使用多个循环更快的匹配方式。我看过an explanation here但这对我来说完全没有意义。

谁能帮我分解一下，target - arr[i] 的用途是什么？

const arr = [7, 0, -4, 5, 2, 3];

const twoSum = (arr, target) => {
  let map = {}
  let results = [];
  for (let i=0; i<arr.length; i++) {
    if (map[arr[i]] !== undefined) {
      results.push([map[arr[i]], arr[i]])
    } else {
      map[target - arr[i]] = arr[i];
    }
  }
  return results;
}
console.log('twoSum = ', twoSum(arr, 5));

Answer 1

假设目标是 t。给定数组中的值 x，您想知道数组中是否存在值 t - x，在这种情况下，总和为 t - x + x = t。

因此，您遍历数组，为了标记您在数组中看到 x 的事实，您在 map 中标记条目 t - x。稍后当您在数组中遇到 t - x 时，您会检查映射中的条目 t - x，如果它已填充，那么您知道您之前看到过 x，这意味着您有 x 和 t - x 对。我刚才描述的方式听起来像是通过数组的两个循环，但您可以在一个循环中完成这两件事，而且它的工作原理是一样的。

如果 map 条目已填充，那么您之前会看到它的对值，如果未填充，则标记 map 以查看稍后是否遇到该对值。