Codility TapeEquilibrium Python解法O(N²)性能优化咨询

原有方案的核心问题 #

你的三个实现时间复杂度均为O(n²)，性能不通过的核心原因和列表append、生成器写法无关，问题出在循环内的重复求和操作：

• 每次循环都对A[:x]和A[x:]两个切片调用sum()，sum()每次执行都需要遍历对应切片的所有元素，加上切片本身会生成新数组产生拷贝开销
• 数组长度为n时，循环执行n-1次，总遍历元素次数为n(n-1)/2量级，数据规模稍大就会超时
• 第三个版本甚至在单次循环内重复计算了3次相同的求和差值，性能反而更差

优化思路 #

利用数学关系减少重复计算：

1. 先一次遍历算出数组所有元素的总和，时间开销O(n)
2. 从左到右遍历分割点时，持续累加左半部分的和，右半部分的和可以直接用总和 - 左半部分和得到，不需要再遍历右半段
3. 遍历过程中只维护当前遇到的最小差值，不需要存储所有差值，把空间开销降到O(1)
4. 注意分割点不能取数组最后一个元素，否则右半部分为空不符合题目要求

优化后实现（O(n)时间复杂度） #

def solution(A):
    total_sum = sum(A)
    left_sum = 0
    min_diff = float('inf')
    # 遍历到倒数第二个元素即可，保证右半段非空
    for num in A[:-1]:
        left_sum += num
        right_sum = total_sum - left_sum
        current_diff = abs(left_sum - right_sum)
        if current_diff < min_diff:
            min_diff = current_diff
    return min_diff

性能说明 #

该实现仅需要两次遍历数组（第一次算总和，第二次遍历分割点），总时间复杂度O(n)，没有额外的数组切片拷贝开销，常数项极低，完全可以通过对应平台的性能测试用例。

内容的提问来源于stack exchange，提问作者LuizGTVSilva