algorithm - 我的数组等边算法意外结果

Question

给定一个数组，找到一个索引 N，其中 N 左侧整数的总和等于 N 右侧整数的总和。如果没有索引可以实现这一点，则返回 -1 .我得到了意想不到的结果。

我尝试了不同的方法来枚举，但一些特殊情况给我带来了麻烦。

def find_even_index(nums):
    total = sum(nums)
    if total%2 != 0:    
        return -1
    total /= 2
    L = 0
    for i, v in enumerate(nums):
        L += v
        if L == total:
            return i
        if L > total:  
            break     
    return i

测试用例 1:[10,-80,10,10,15,35,20] 应该给出 6 但返回 0
测试用例 2:range(1,100) 应该给出 -1 但返回 69
测试用例 3:[-1,-2,-3,-4,-3,-2,-1] 应该给出 3 但返回 0

Answer 1

我的解决方案是这样的:

t = [-1,-2,-3,-4,-3,-2,-1]


def find_even_index(nums):
    sum = 0
    f = []

    for idx, val in enumerate(nums):
        if idx == 0:
            f.append(val)
        else:
            f.append(f[idx-1] + val)
        sum += val

    for idx, val in enumerate(nums):
        t = 0
        if idx != 0:
            t = f[idx - 1]
        if t == sum - f[idx]:
            return idx

    return -1


print find_even_index(t)

我使用了部分求和算法。它是这样工作的:你计算从 0 到索引 X 的总和。然后你可以知道任何一对索引 (i, j) 之间的总和。