试图在数组中查找左侧元素和右侧元素之和相等的元素。你能优化我的方法吗？

Question

def balancedSums(arr):
    n = len(arr)
    for i in range(0, n):
        lsum = sum(arr[0 : i])
        rsum = sum(arr[i + 1 : n])
        if lsum == rsum:
            return "YES"
    return "NO"

我正在获取除两个之外的所有测试用例，由于超时而失败。我有什么选择

Answer 1

你可以这样做：

def balancedSums(arr):
    lsum = 0
    rsum = sum(arr)
    n = len(arr)
    for i in range(0, n):
        rsum -= arr[i]
        if lsum == rsum:
            return "YES"
        lsum += arr[i]
    return "NO"

其时间复杂度为O(n)