为 Code Wars 优化零件总和函数

Question

我正在查看 CodeWars 上的 Sums of Parts 问题：

Let us consider this example (array written in general format):
ls = [0, 1, 3, 6, 10]
Its following parts:
ls = [0, 1, 3, 6, 10]
ls = [1, 3, 6, 10]
ls = [3, 6, 10]
ls = [6, 10]
ls = [10]
ls = []
The corresponding sums are (put together in a list): [20, 20, 19, 16, 10, 0]

The function parts_sums (or its variants in other languages) will take as parameter a list ls and return a list of the sums of its parts as defined above.

函数的目标是对数组的元素求和，然后每次移动数组的第一个元素，直到数组的长度变为0。

我有这个解决方案：

function partsSums(ls) {
    let len = ls.length;
    let arr = [];
    for (let i = 0; i < len +1; i++) {
        arr.push(summation(ls));
        ls.shift();
    }

    function summation(a) {
        let sum = 0;
        for (let i = 0; i < a.length; i++) {
            sum += a[i];
        }
        return sum;
    }
    return arr;
}

当我在我的编辑器中运行它时它起作用了：CodeWars 上所有成功完成的测试用例都通过了，但是当我尝试提交时，我得到这个错误：

Process was terminated. It took longer than 12000ms to complete

我是算法新手，不明白错误在哪里？欢迎提出任何建议。

Answer 1

The goal of the function is to sum elements of array then shift the first element of array each time until the length of array become 0

代码挑战实际上并没有谈到移位。您可以通过立即将值存储在结果数组中的正确索引处来执行此操作而无需移位。此外，您的函数 summation 正在重复对一些相同的值求和。这是可以避免的。

举个例子：

ls = [0, 1, 3, 6, 10]

输出可以构造如下：

创建一个长一个元素的数组，最后的值为 0:
```
ls:     0  1  3  6 10
result: .  .  .  .  .  0
```
（此时点处的值不相关）
然后从右边开始，创建一个（向后）运行总和：
```
ls:     0  1  3  6 10
result: ↓  ↓  ↓  ↓  ↓← 0
        ↓  ↓  ↓  ↓←10
        ↓  ↓  ↓←16
        ↓  ↓←19
        ↓←20
       20
```
因此索引 i+1 的先前结果被添加到索引 i 的输入，因此它向后计算到数组的开头。

这是一个实现：

function partsSums(ls) {
    let result = Array(ls.length + 1).fill(0);
    for (let i = ls.length - 1; i >= 0; i--) {
        result[i] = ls[i] + result[i + 1];
    }
    return result;    
}

为 Code Wars 优化零件总和函数

Optimizing Sums of Parts function for Code Wars

javascript

algorithm

optimization

performance