成对求和挑战

Question

我有可用的代码，但我希望改进我理解和实施不同编码技术的方式。我认为这个问题提供了一个很好的机会来获得关于我正在做的事情的反馈。

这里的想法是采用两个参数，一个数组和一个整数。确定数组中所有对的总和以构成整数参数，然后 return 索引的总和。您不能重复使用索引，您必须始终使用可用的最小索引。这里有关于 FCC 代码指南的解释：https://www.freecodecamp.org/learn/coding-interview-prep/algorithms/pairwise

所以 - 这是问题。有没有不使用嵌套 for 循环的好方法？我越来越意识到 time/space 的复杂性，而且我知道 O(n^2) 不会让我找到这份工作。我想它会出现某种哈希图，但我只是没有经验和知识来知道如何使用它们。

代码如下：

function pairwise(arr, arg) {

  let usedIndex = [];
  let output = 0;

  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (
          arr[i] + arr[j] == arg
          && usedIndex.indexOf(i) == -1
          && usedIndex.indexOf(j) == -1
        ) { 
          usedIndex.push(i, j)
          output += i + j
      }
    }
  }

  return output;

}

pairwise([0, 0, 0, 0, 1, 1], 1) // should return 10

Answer 1

为了获得更好的性能，您可以将 arr.length 保存到一个变量中，这样 for 循环就不会计算每个循环。

function pairwise(arr, arg) {

  let usedIndex = [];
  let output = 0;
  let length = arr.length;

  for (let i = 0; i < length; i++) {
    for (let j = i + 1; j < length; j++) {
      if (
          arr[i] + arr[j] == arg
          && usedIndex.indexOf(i) == -1
          && usedIndex.indexOf(j) == -1
        ) { 
          usedIndex.push(i, j)
          output += i + j
      }
    }
  }
  return output;
}

Answer 2

这可以在一个循环中完成，巧妙地使用一个对象并了解索引只能使用一次。

function pairwise(arr, arg) {
  let map = {};
  let output = 0;
  let length = arr.length;

  for (let i = 0; i < length; i++) {
    let subArr = map[arr[i]];
    if(subArr && subArr[0] !== undefined) {
      //there is an index waiting to pair, remove it and add to output
      output += subArr.pop() + i;
    } else {
      //add this index to its pair slot
      let left = arg - arr[i];
      if(!map[left]) map[left] = [];
      map[left].unshift(i);
    } 
  }

  return output;
}

console.log(pairwise([0, 0, 0, 0, 1, 1], 1), "should be 10");
console.log(pairwise([1, 4, 2, 3, 0, 5], 7), "should be 11");
console.log(pairwise([], 100), "should be 0");
console.log(pairwise([1, 3, 2, 4], 4), "should be 1");

映射的键代表构成一对所需的另一个值，映射的值是具有构成一对的值的索引数组。使用 unshift() 插入索引，以便 pop() returns 插入的第一个 - 最小的。

从前面迭代保证首先找到最小的对，映射保证任何后面的索引将确切地知道可以形成对的最早索引是什么。

Answer 3

对列表进行排序。
有两个柜台从两端走。在每一步检查总和是否是您想要的。如果是这样，请捕获所需的指标。

第 1 步是 O(n*logn)。

第 2 步是 O(n) - 每个计数器将在列表中进行大约一半，在它们相遇时停止。

成对求和挑战

Pairwise sums challenge

javascript

time-complexity

nested-loops

ecmascript-6