时间戳

首页 > 解决方案 > 如果数组的任何元素等于 n 或数组的两个元素之和等于 n，则返回 true - 提高性能

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

问题描述

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

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

它工作正常，但在性能方面使用“一些”最好的方式？如何提高执行速度？

编辑：允许负数

标签： javascriptecmascript-6

解决方案

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

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

在诉诸于此之前，我建议降低您的时间复杂度：Array#includesis O(n), as is Array#slice. 在嵌套循环中执行这些操作是 O(n^2)。

您可以尝试经典的“空间与时间”权衡，并使用集合来存储您目前看到的每个元素。如果n - currentElement === something in the set，您已找到两个总和为 的数字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));

请注意，这是“二和”问题的轻微变体。

推荐阅读