Subsequence sum

Make a new array with each element equal to the sum of the previous elements plus that one.

Input:

1  4 -3 -4  6  -7  8 -5

Becomes:

1  5  2  -2  4  -3  5  0
   ^                ^

Then look for elements that match in the resulting array.

Since these represent locations where the overall change in the function is zero, you will find that if their position is i and k then the subsequence (i+1, k) is a zero-sum subsequence. (In this case, [2:6]).

Additionally, any zeros in the table indicate that the subsequence (0, k) is a zero-sum subsequence. For the lookup, a hash table or other fast collision locator makes this O(N) to perform.

Do a running sum, storing sum values in a hash table along with array index

If you ever get a sum value you’ve already seen, return 1+the index in the hash table, and the current index. This solution is O(n) time complexity.

No need for a new array. Space complexity is O(N) because of the hash.

---

A Python implementation:

input = [1, 4, -3, -4, 6, -7, 8, -5]
map = {}
sum = 0
for i in range(len(input)):
    sum += input[i]
    if sum in map:
        print map[sum][0] + 1, "to", i
    map[sum] = (i, sum)

Notice that repeated subsequences are not shown, example: If (1 to 2) is a subsequence and (3 to 4), (1 to 4) won't be shown. You can achieve this behavior by storing lists in each position of the map:

for x in map[sum]:
    print x[0]+1, "to", i
map[sum].append((i, sum))