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

问：

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

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

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

然后求和到最后。1+etc

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

但我不想用数字本身来求和。

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

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

例子：

对于输入，我期望（按任何顺序），因为、和。[5,1,3[6, 8, 4]5+1=65+3=81+3=4
对于我期望的输入（按任何顺序），因为、、、和。[5,1,3,2][6, 8, 7, 4, 3, 5]5+1=65+3=85+2=71+3=41+2=33+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]

JavaScript 数组算法

评论

1赞 pilchard 10/22/2023

@Kamo 正如下面的答案所指出的，这没有线性解决方案，因为总会有二次求和要完成。

0赞 Kamo 10/22/2023

@T.J.Crowder：我现在可以看到，以线性方式实现这一点可能是不可能的

答：

-5赞 grief kid 10/22/2023 #1

在为第一个元素创建结果时，可以创建第二个结果。

当您为第一个元素创建第二个结果时，您可以忽略第一个元素，这是第二个元素的第一个结果，等等......

你知道的？

评论

0赞 Kamo 10/22/2023

在这样做时，每个元素总和都会有自己的数组？

0赞 grief kid 10/22/2023

是的，这是正确答案。我不知道-1是什么！

5赞 Ayoub k 10/22/2023 #2

您可以稍微优化代码，使其在 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）时间复杂度。我不确定您是否可以在不使用嵌套循环的情况下获得所需的结果。

评论

0赞 Kamo 10/22/2023

我知道这种方法是二次的，尽管我需要一种方法来实现它是线性的。

2赞 pilchard 10/22/2023

@Kamo 要完成的总和是二次，因此任何解都将是 O（n^2）

上一个：DFS 最终进入无限循环

下一个：要排序的二进制字符串的最小替换项