[Java] Subarray of sum K

Given an array of integers with duplicates, negatives and zeros, find a subarray that reaches a target sum.

The sum must be formed by at least two elements.

Example:

2, -1, -2, 5

target 5, no result

target -3, one result: -1,-2

The linear time approach builds upon this observation: having the rolling sum (prefix sum) for each position, if at any point the current sum - target results in an already seen sum, it means there are two subarray sums whose difference is exactly K, which implies there is a subarray whose sum is exactly K.

We can see the current sum as every element from the first to the current element and wonder whether we can use any previous sum (which is contained in the current one) to calculate the middle portion between that sum and the current index.

This however could be a single element, therefore we can't use a simple Set to track this information. If we use a Map instead to store pairs: sumAtIndex, Index we can then easily check whether the subarray we would consider as result has at least two elements: index - indexOfSum must be greater than 1.

Specifically:

if currentSum (curr) - K = any of the previous prefix sums (other), there is a subarray between other and curr whose sum is K.

To avoid the case where the first element is equal to K, we must initialize the map to (0, -1).

It took a while to visualize this, in our example with K = -3:

• get 2, rolling sum is 2 check 2 - K = 5 which is not in the map, put current sum in map and continue

current subarray sum is made of elements: 2

map = (0,-1), (2,0)

• get -1, rolling sum is 2 - 1 = 1, check 1 - K = 4 which is not in the map, put current sum in map and continue

current subarray sum is made of elements: 2 , -1

map = (0,-1), (2,0) , (1,1)

• get -2, rolling sum is 1 - 2 = -1, check -1 - K = 2 is in the map

current subarray sum is made of elements: 2 , -1, -2. We have the sums of subarrays (2), (2, -1) stored.

Could we remove any of those sums to retrieve the sum of elements between those subarrays and ourselves? Yes in O(N) time, but we don't need to check all of them as we are only interested in knowing whether any subarray in between sums up to K so we can approach it from the opposite direction. If we remove K from the current sum, we are deleting (if any) a subarray in the middle whose sum is K.

If that subarray existed, we sould reach a prefix sum we've already seen. In this case from current subarray sum (2, -1, -2) we remove K (-3) which corresponds to subarray (-1, -2) and are left with sum of 2 which was subarray (2). Therefore between (2) and current index we had (-1, -2) which is our answer.

We just need to check if that subarray is formed by more than one element:

index of sum 2 is 0, current index is 2. 2 - 0 is greater than 1 so that subarray contains at least two element, we can stop.

You can check my implementation of subarrayOfSumK on my Gist along with some tests in SubarrayOfSumKJTests.