Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number.
The subarray should contain at least one integer.
[-3, 1, 2, -3, 4], return
[0, 2] or
A simple solution is to have two array index pointers and check every possible subarray. When a subarray sums to 0, we return the two index pointers as the result. This algorithm has O(n2) time complexity and we can do better.
A more efficient algorithm is to keep a running sum from the beginning of the array and use an HashMap to track the running sum for each index of the array, as shown in the figure below.
nums: -3 1 2 -3 4 sum : -3 -2 0 -3 1 nums: 3 2 -1 -1 1 sum : 3 5 4 3 4
There are two scenario where we found the zero-sum subarray:
- When the running sum is 0. In this case, we know the zero-sum subarray is from index 0 to the current index.
- When a sum is already in the HashMap. In this case, the subarray between the index where we last found the sum to the current index, is a zero-sum subarray, because this subarray essentially contributed nothing to the running sum.
This algorithm has time complexity of O(n) and the implementation is listed below.