编码挑战速度问题。从 2 个数组中查找与给定总和匹配的元素

Question

你有两个整数数组a和b，以及一个整数目标值v。确定是否有一对数字，其中一个数字取自a，另一个取自b，可以加在一起得到得到 v 的总和。Return 如果存在这样的对，则为真，否则 return 为假。

例子

对于 a = [1, 2, 3]，b = [10, 20, 30, 40] 和 v = 42，输出为真，因为 40 + 2 = 42。

以上是我的问题。我有正确的解决方案，但我想要一种更好的方法来编写解决方案...我希望它运行更快。我目前正在使用两个 for 循环：

function sumOfTwo(a, b, v) {
    for(var i=0; i < a.length; i++) {
        for(var j=0; j < b.length; j++) {
            if(a[i] + b[j] === v) {
                return true;
            }
        }
    }
    return false;
}

感谢任何帮助！

Answer 1

用蛮力检查是 O(n*n)

对两个数组进行排序。从小于v的元素开始往递减的方向去。（其他肯定会溢出）排序可以是O(nLogn)

 a ---> a'   O(nlogn)
 b ---> b'   O(nlogn)

binary search to elliminate a(i) > v and b(i)>v O(logn)

现在您要继续的价值要少得多，因为 O(n*n)

Answer 2

如果您首先从数组 a 创建一个包含 v - a[i] 结果的集合，则可以实现线性复杂度。这需要 O(len(a)).

然后您遍历 b，并检查是否存在 set.get(b)，即 v - a[i]。如果是，那么 v - a[i] === b[i] 所以 a[i] + b[i] === v。这需要 O(len(b)).

因此总复杂度为 O(len(a)) + O(len(b))（检查集合中的存在性为 O(1)）。

由此可知，如果数组长度相等，则复杂度为O(2N)，即O(N)。

代码如下：

function sumOfTwo(a, b, v) {
  const setOfRemaindersFromA = new Set(a.map(num => v - num));
  return b.some(num => setOfRemaindersFromA.has(num));
}

const a = [1, 2, 3, 4],
      b = [10, 20, 30, 40];
      
console.log(sumOfTwo(a, b, 42)); // true
console.log(sumOfTwo(a, b, 45)); // false

注意：查看以获得此方法的 ES6 之前的解决方案。

如果数组可以有不同的长度，您必须从较短的数组构建集合并迭代较长的数组以确保覆盖所有元素。

比较数组长度是一个常量操作，因此这不会影响整体复杂性。

function sumOfTwo(a, b, v) {
  const [shorter, longer] = a.length > b.length ? [b, a] : [a, b];
  const setOfRemaindersFromShorter = new Set(shorter.map(num => v - num));
  return longer.some(num => setOfRemaindersFromShorter.has(num));
}

const a = [1, 2],
      b = [10, 20, 30, 40];
      
console.log(sumOfTwo(a, b, 42)); // true
console.log(sumOfTwo(a, b, 45)); // false

Answer 3

谢谢！！我尝试了以下方法：

function sumOfTwo(a, b, v) {
    var a = a.sort();
    var b = b.sort();
    for(var i=0; i < a.length; i++) {
        for(var j=b.length - 1; j >= 0; j--) {
           if(a[i] > v && b[j] < v) {
                break;
            }
            if(a[i] + b[j] === v) {
                return true;
            }
        }
    }
    return false;
}

请告诉我是否可以进一步改进！

Answer 4

将其中一个数组转换为由值索引的数组。然后循环另一个数组，判断v - element是否是数组的元素

function sumOfTwo(a, b, v) {
    var test = [];
    for (var i = 0; i < a.length; i++) {
        test[a[i]] = true;
    }
    for (var i = 0; i < b.length; i++) {
        if (test[v - b[i]]) {
            return true;
        }
    }
    return false;
}

Answer 5

通过散列和查找传递它

function sumOfTwo(a, b, v) {
    const x = a.reduce( (o,a) => { o[a]=1; return o; }, {})
    return b.some( b => { return x[v-b] })
}

如果数组已排序，如果值大于 v

，可能会加快速度以跳出循环

编码挑战速度问题。从 2 个数组中查找与给定总和匹配的元素

Coding Challenge Speed Issue. Find elements from 2 arrays matching a given sum

javascript

arrays

performance

big-o

time-complexity