Find index where left sum equals to right sum Given an array, find if there is an index where left sum equals to right sum.


My idea is calculate sum, and scan again to see if there is an index for which left_sum equals to total_value - left_sum. My code needs to scan the array twice. I'm wondering if there are any solutions which only need to scan the array once.

import random
def find_index(nums):
    total_value = sum(nums)
    left_sum = 0
    for i,v in enumerate(nums):
        left_sum += v
        if total_value - left_sum == left_sum:
            return i
    return -1

if __name__ == "__main__":
    nums = []
    for i in range(10):
        nums.append(random.randint(0,5))
    print nums
    print find_index(nums)
Two minor improvments are possible:
1- splitting an array by the sum of the elements only makes sense if the elements are integers. Two equal sums of elements require the total sum over all elements to be even. Check this to shortcut the search.
2- if all elements are positive we can further shortcut the search (see comment).
On my notebook this cuts the runtime to ~ 1/3 for short arrays (len=200) and ~2/3 for long arrays (len=20k).  

def find_index2(nums):
    total = sum(nums)
    if total%2 != 0:    # this shortcut only if integer array
        return False, -1
    total /= 2
    L = 0
    for i, v in enumerate(nums):
        L += v
        if L == total:
            return True, i
        if L &gt; total:  # this shortcut only if only positive values in array
            break
    return False, i


edit:
Observing that sum() is faster than elementwise summation I changed the algorithm a bit. Now the majority (here: 50%) of the elements are summed up in one call to sum() and then the exact target value is searched for step by step. Also, I have incorporated @kyrill's comments to remove the restriction for integer values. Still, the assumed property of only positive values is used (see code comments).
Execution time is down to approximately 20% vs. OP's code:    

def find_index8(nums):
    total = sum(nums) / 2.
    n = int(len(nums) * .5)  # arbitrary, well-guessed testing index
    S = sum(nums[:n])
    if S == total:
        return True, n-1
    elif S &lt; total:                 # add elementwise
        for i, v in enumerate(nums[n:], n):
            S += v
            if S &gt;= total:    # '&gt;' shortcut only if only positive values in array
                return S==total, i
        return False, -1
    else:                 # subtract elementwise
        for i, v in enumerate(nums[:n][::-1], 2):
            S -= v
            if S &lt;= total:    # '&lt;' shortcut only if only positive values in array
                return S==total, n-i
        return False, -1