To find the longest subarray with a given sum k
, especially when the array can have both positive and negative integers, we use a strategy based on prefix sums and a hash map.
Here’s the idea: As we traverse the array, we keep track of the cumulative sum (also called prefix sum) up to the current index. For each prefix sum, we store the first index where it occurred in a hash map.
Understanding the Intuition
Suppose at index i
, the prefix sum is curr_sum
. If there exists a prefix sum at an earlier index j
such that:
curr_sum - prefix_sum[j] = k
then the subarray from index j+1
to i
has a sum of k
. By storing the first occurrence of each prefix sum in a map, we can look this up quickly and determine the length of such subarrays.
What Happens in Different Cases?
- Exact match from the start: If the prefix sum itself becomes
k
, then the subarray from index 0
to i
is valid. We track this using i + 1
.
- Zero sum cases: When the target sum is
0
, the logic still works because the prefix sum might repeat, and the difference is 0.
- All elements are zeros: If the entire array is zeros and the target is also zero, the whole array is the valid longest subarray.
- No matching sum found: If we go through the array and never find a prefix sum that helps us build a valid subarray with sum =
k
, we return 0
.
- Empty array: If the array is empty, there’s no subarray at all, so the answer is
0
.
Using this method ensures that we consider all possible subarrays without checking each one manually, and we do so efficiently with a time complexity of O(n).
This solution works great even with negative numbers, unlike sliding window techniques that require non-negative elements.