将一个数字与数组中的其他数字相加

Question

我得到了一组数字，[5,1,3, etc, etc]。

我想将5+1结果求和并保存在名为 的新数组中results，然后求和5+3并保存结果，然后求和5+etc直到达到最后一个数字。

之后我想总结1+3并保存结果。

然后求和1+etc到最后。

然后求和3+etc，直到到达最后一个，依此类推......

但我不想将一个数字与其自身相加。

数组中数字的顺序results并不重要，重要的是返回的数组中存在预期的数字。

我想在不使用嵌套循环的情况下实现这一目标，以保持线性时间复杂度。

例子：

• 对于输入[5,1,3]，我期望[6, 8, 4]（以任何顺序），因为5+1=6、5+3=8和1+3=4。
• [5,1,3,2]对于我期望的输入[6, 8, 7, 4, 3, 5]（以任何顺序），因为5+1=6、5+3=8、5+2=7、1+3=4、1+2=3和3+2=5。

我试过这个：

function sumTwo(arr) {
  
  const results = []

  for(let i = 0; i < arr.length - 1; i++) {
    let sum = arr[i] + arr[i + 1]
    results.push(sum)
  }
  console.log(results)
}

console.log(sumTwo([5, 1, 3]));

...但它给了我错误的输出（[6,4]而不是[6,8,4]）。

Answer 1

您可以稍微优化代码，使其在 O(n^2) 边界内更加高效。一种可能的方法是使用滑动窗口的概念。但同样，它不会将时间复杂度降低到 O(n)。

function sumTwo(arr) {
  const results = [];

  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      results.push(arr[i] + arr[j]);
    }
  }
  return results;
}

const output = sumTwo([5, 1, 3]);
console.log(output); // outputs: [6, 8, 4]

这不会帮助您逃避 O(n^2) 时间复杂度。我不确定您是否可以在不使用嵌套循环的情况下获得所需的结果。