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

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

我试着想出一种矢量化的方法来使用Numpy实现这一点。这是迄今为止我想到的最好的：

import numpy as np

def balancedSums(arr):
    arr = np.array(arr)
    ltr = np.cumsum(arr)
    rtl = np.cumsum(arr[::-1])[::-1]
    if np.any(ltr == rtl):
        return "YES"
    else:
        return "NO"

assert(balancedSums([1, 2, 3]) == "NO")
assert(balancedSums([3, 2, 1, 2, 3]) == "YES")
assert(balancedSums([10]) == "YES")
assert(balancedSums([1, 1]) == "NO")
assert(balancedSums([0]) == "YES")
assert(balancedSums([]) == "NO")

Answer 2

你可以这样做：

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)