Question

link

Given an array of positive and negative numbers, find if there is a subarray with 0 sum.

eg. 4, 2, -3, 1, 6 -> return true (2, -3, 1)

eg. 4, 2, 0, 1, 6 -> return true (0)

Solution

General case, idea of 前缀和:

iterate through the array and for every element arr[i], calculate sum of elements form 0 to i (this can simply be done as sum += arr[i]). If the current sum has been seen before, then there is a zero sum array.

O(n) time.

Special Case, if the input is all positive number, then this question can be solved using the idea from Subarray with Particular Sum, O(n) time.