LC: Maximum Size Subarray Sum Equals k - spiralgo/algorithms GitHub Wiki

Maximum Size Subarray Sum Equals k

The Essence:

A maximum Size subarray sum that equals k is an equivalent expression to this:

• The sum of all numbers up to a certain index i equals to some sum s.
• If we subtract k from s, and the result was previously encountered at some index j, that means that we have a subarray of length i-j that equals to k.

We can illustrate this with an example: Consider the array [7, 1, -2, 5, -1, 3] and the value k = 3. The current sum at index i = 4 is (7+1+(-2)+5+(-1)) = 10. When subtract k from this current sum, we get 7. We have previously encountered 7 at the index j = 0. So, i-j = 4 will yield us a range of 4.

Details:

The first index that has the remaining sum can be checked using hash tables or arrays. It's important to note that, for the sum = 0, it should be assumed that this does occur at the index -1.

Further explanation and implementation can be found here: https://github.com/spiralgo/algorithms/pull/291