Longest Subarray with Sum K
Given an array (may contain negatives) and a target k, return the length of the longest subarray whose elements sum to exactly k.
Intuition
Every subarray sum is a difference of two prefix sums: sum(i..j) = pre[j] − pre[i−1]. So a subarray sums to k exactly when the current prefix minus some earlier prefix equals k. Store the first index where each prefix value occurred, and each new prefix asks: have I seen prefix − k before?
Approach
Why sliding window fails here
With negatives, growing the window can shrink the sum and shrinking can grow it — the window has no monotone signal to steer by. We need something that works for arbitrary signs: prefix sums.
Prefix sums turn subarrays into pairs
Walk once keeping the running sum pre. If some earlier prefix equaled pre − k, the elements after that point sum to exactly k. A hash map from prefix value → earliest index answers that in O(1).
Keep only the first occurrence
For the longest subarray we want the earliest index where each prefix value appeared, so never overwrite an existing entry. Seed the map with {0: -1} so subarrays starting at index 0 are counted.
Solution & live demo
Edge cases
The seed {0: -1} makes pre == k yield length i − (−1) = i + 1.
Keep the first index only — a later duplicate would only shorten the candidate subarray.