Implement the longestSubarrayZeroSumLength method that returns the length of the longest subarray with sum zero.
The input contains an integer array nums and its length size. Your task is to return the length of the longest continuous subarray whose sum is 0.
A subarray must contain consecutive elements from the original array.
For example, in [15,-2,2,-8,1,7,10], the subarray [-2,2,-8,1,7] has sum 0 and length 5.
Example 1
Input
nums (int[]) =
[15,-2,2,-8,1,7,10]size (int) =
7Returns (int)
5Example 2
Input
nums (int[]) =
[1,-1,3,2,-2,-3]size (int) =
6Returns (int)
6Example 3
Input
nums (int[]) =
[1,2,3]size (int) =
3Returns (int)
0Use prefix sums and remember the first index where each prefix sum appeared.
If the same prefix sum appears again later, the values between the first occurrence and the current index must have sum 0. This is because the total sum before and after that subarray is the same.
Keep the earliest index for each prefix sum so the subarray length can be as large as possible.
Pseudocode:
function longestSubarrayZeroSumLength(nums, size):
create empty map firstIndex
firstIndex[0] = -1
sum = 0
best = 0
for i from 0 to size - 1:
sum = sum + nums[i]
if sum exists in firstIndex:
length = i - firstIndex[sum]
best = maximum(best, length)
else:
firstIndex[sum] = i
return bestReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run