Longest Subarray With Sum K

Given an array of n integers, which may include negative numbers, and an integer k, find the length of the longest contiguous subarray whose elements sum to exactly k. If no such subarray exists, print 0.

Input: The first line contains two space-separated integers n and k. The second line contains n space-separated integers. Output: A single integer: the length of the longest subarray summing to k, or 0 if none exists.

1 <= n <= 10^5. -10^4 <= arr[i] <= 10^4. -10^9 <= k <= 10^9.

This exact 'prefix sum plus hash map of first occurrences' technique directly generalizes to other sum-based subarray problems (like 'Longest Subarray With Equal 0s and 1s', which is really the same technique after remapping 0s to -1s) - recognizing the shared pattern connects several seemingly different problems.

Find the length of the longest contiguous subarray (which may include negative numbers) whose elements sum to exactly a target K. Brute force: Check every possible contiguous subarray directly, summing each and tracking the longest one that hits exactly k - this costs O(n²), too slow for large arrays. Optimised: Since subarray[i+1..j]'s sum equals prefix[j] - prefix[i], checking whether (current prefix - k) has appeared EARLIER via a hash map instantly identifies a valid subarray ending at the current position - storing only the FIRST occurrence of each prefix sum value guarantees the LONGEST possible subarray is found for each valid match.

1. Compute the RUNNING PREFIX SUM as you scan the array from left to right. 2. For each prefix sum, check whether (current prefix sum - k) has occurred EARLIER in a hash map - if it has, the subarray between those two points sums to exactly k. 3. Store only the FIRST index at which each prefix sum value occurs, since that choice maximizes the resulting subarray length.

Time: O(n) - one single pass, with O(1) average-case hash map lookups. Space: O(n), for the hash map of prefix sums to their first occurrence index.

Negative numbers mean a longer subarray does not always have a larger sum. If k never occurs as any subarray sum, print 0.

Be ready to explain precisely WHY storing only the FIRST occurrence (not overwriting on later duplicates) is essential - overwriting would only ever produce a SHORTER subarray, since a later starting point can never extend further back than an earlier one.