如何对每个数组中的每个数字彼此求和？

Question

在Hackerrank中，这是一个叫做电子商店的挑战，这是我的代码，它可以在一定程度上进行测试。当输入增加时，编译时间变得更长。所以我需要将一个数组中的每个数字与第二个数组中的其他数字相加。

​

function getMoneySpent(keyboards, drives, b) {
  let purchase = [];
  let result = -1;

  for(let i = 0; i < keyboards.length; i++) {
   for(let j = 0; j < drives.length; j++) {
     if((keyboards[i] + drives[j]) <= b) {
      purchase.push(keyboards[i] + drives[j]);
       result = Math.max(...purchase);
      } 
    }
   }
   return result;
}

console.log(getMoneySpent([4], [5], 5)); // Should return  -1
console.log(getMoneySpent([3, 1], [5, 2 ,8], 10)); //Should return  9
console.log(getMoneySpent([40, 50, 60], [5, 8, 12], 60)) // Should return  58

​

我不知道如何让它更有效率。

Answer 1

一个细微的改进是不使用purchase数组，而是仅对当前最佳结果和新结果调用Math.max：

​

function getMoneySpent(keyboards, drives, b) {
  let result = -1;

  for (let i = 0; i < keyboards.length; i++) {
    for (let j = 0; j < drives.length; j++) {
      const newResult = keyboards[i] + drives[j];
      if (newResult < b) {
        result = Math.max(result, newResult);
      }
    }
  }
  return result;
}

console.log(getMoneySpent([4], [5], 5)); // Should return  -1
console.log(getMoneySpent([3, 1], [5, 2, 8], 10)); //Should return  9
console.log(getMoneySpent([40, 50, 60], [5, 8, 12], 60)) // Should return  58

​

一种可以降低计算复杂度的更精细的方法是，首先对两个数组进行排序，然后从末尾开始对两个数组进行比较索引：

xxxxxxxx
       ^
yyyyyy
     ^

选择其中一个数组并递减索引，直到到达总和低于b的点

xxxxxxxx
       ^
yyyyyy
   ^  

然后递减另一个索引，同时尽可能增加当前索引，直到第一个索引再次位于末尾：

xxxxxxxx
   ^
yyyyyy
     ^

并在递增时在找到的限制内采用最大的组合。

由于.sort的原因，这种方法会有O(n log n)的复杂性(我上面的getMoneySpent是O(n ^ 2))