javascript - 如果数组的任何元素等于 n 或数组的两个元素之和等于 n，则返回 true - 提高性能

Question

如标题所示，如果数组的任何元素等于 n 或数组的两个元素之和等于 n，我想返回 true。因此，如果数组是 [1,4,5] 并且 n 是 1 或 4 或 5 或 6 或 9 我想得到 true。这是我的代码:

function checkArray (x, array) {
  return array.includes(x) || array.some((item, i) => array.slice(i+1).includes(x-item)); 
}

它工作正常，但就性能而言，使用“some”是最好的方法吗？如何提高执行速度？

编辑:允许负数

Answer 1

除了分配/垃圾收集函数对象并为数组的每个元素旋转函数调用的正常性能开销之外，some 没有任何问题。

使用传统的 for 循环几乎总是最快的，但这通常是一种微观优化，只能用作最后的手段 - 从惯用的高级回调驱动进行重构for 循环的 JS 代码仅提供恒定因子加速。

在采取这种方法之前，我建议降低时间复杂度:Array#includes 是 O(n)，Array#slice 也是如此。在嵌套循环中执行这些操作的时间复杂度为 O(n^2)。

您可以尝试经典的“空间与时间”权衡，并使用一个集合来存储您迄今为止看到的每个元素。如果n - currentElement === 集合中的某些内容，则您已找到总和为n 的两个数字。

const oneOrTwoElementsEqualN = (arr, n) => {
  const seen = new Set();
  return arr.some(e => {
    if (e === n || seen.has(n - e)) {
      return true;
    }
    
    seen.add(e);
  });
};

console.log(oneOrTwoElementsEqualN([1,2,3], 5));
console.log(oneOrTwoElementsEqualN([1,2,3], 2));
console.log(oneOrTwoElementsEqualN([1,2,3], 6));

请注意，这是 "two sum" 的一个轻微变体。问题。