subarray with sum 0 in array

//example

  |    |
1 3 -5 2

  |
1 0 1

Naive approach. Get the longest subarray.

// time: O(n^2)
(a):
    maxstart = 0, maxend = -1
    for i = 0, i < a.length(), i++:
        sum = 0
        for j = i, j < a.length(), j++:
            sum += a[j]
            if sum == 0:
                if j-i > maxend-maxstart:
                    maxstart = i
                    maxend = j
    if maxend == -1:
        return -1, -1
    return maxstart, maxend

Better approach is to keep the running sum and a map of sum->i. If sum exists in map, then subarray is from map[sum]+1 to i.

Get the longest subarray.

//example
  i: 0 1  2  3  4  5 6 7 8
  a: 1 7  3 -5 -5 -3 3 3 2
sum: 1 8 11  6  1 -2 1 4 6
       |--------|
       |-------------|
                |--------|

// time O(n), space O(n)
(a):
    maxstart = 0, maxend = -1
    sum = 0
    sumtoindexMap = new // int->int
    sumtoindexMap[0] = -1
    for i = 0, i < a.length(), i++:
        sum += a[i]
        if sumtoindexMap.has(sum):
            start = sumtoindexMap[sum] +1
            end = i
            if end-start > maxend-maxstart:
                maxstart = start
                maxend = end
        else:
            sumtoindexMap[sum] = i
    if maxend == -1:
        return -1, -1
    return maxstart, maxend

Get all subarrays.

//example
  a: 0 -1 1 0
sum: 0 -1 0 0
     |
     |----|
        |-|
     |------|
        |---|
            |

// time O(n), space O(n)
(a):
    subarrays = new list()
    sum = 0
    sumtoindexsMap = new // int->list{int}
    sumtoindexsMap[0] = [ -1 ]
    for i = 0, i < a.length(), i++:
        sum += a[i]
        indexs
        if !sumtoindexsMap.trygetvalue(sum, out indexs):
            indexs = new
            sumtoindexsMap[sum] = indexs
        else:
            for index in indexs:
                subarrays.add(tuple(index +1, i))
        indexs.add(i)
    return subarrays