Codewars parts_sums函数Runtime error超时问题求助

你当前的parts_sums函数在处理大型列表时超时，核心原因是每次循环调用sum(ls[i:])会重复计算大量元素，时间复杂度为O(n²)，当列表包含数千个元素时，这种重复计算会导致运行时间远超限制。

优化思路 #

改用一次求和+反向递推的方式，将时间复杂度降到O(n)：

1. 先计算列表所有元素的总和，作为第一个后缀和；
2. 依次减去列表中的每个元素，得到后续的后缀和；
3. 遍历结束后自然得到0（所有元素都被减去后的结果）。

优化后的代码 #

def parts_sums(ls):
    result = []
    total = sum(ls)
    result.append(total)
    for num in ls:
        total -= num
        result.append(total)
    return result

效率对比 #

• 原代码中，sum(ls[i:])每次都会遍历从索引i到末尾的所有元素，对于长度为n的列表，总计算量是n + (n-1) + ... + 1 = n(n+1)/2，属于O(n²)的低效算法；
• 优化后的代码只需要两次线性遍历：一次计算总和，一次递推生成所有后缀和，总计算量是2n，属于O(n)的高效算法，能轻松处理数千元素的测试用例。

示例验证 #

以题目给出的测试用例验证：

• 输入ls=[0,1,3,6,10]，输出[20,20,19,16,10,0]，符合要求；
• 输入ls=[1,2,3,4,5,6]，输出[21,20,18,15,11,6,0]，符合要求。

内容的提问来源于stack exchange，提问作者Jaime III Andrade