Longest Subarray With Sum K
mediumArrays & Prefix Sums+20 XPTime limit 2s
Find the length of the longest contiguous subarray whose sum is exactly k. The array may contain negative numbers and zeros.
Input:
- line 1:
n k - line 2:
nintegers
Output: the length of the longest such subarray, or 0 if none exists.
Constraints: 1 ≤ n ≤ 10⁵, −10⁴ ≤ a[i] ≤ 10⁴, −10⁹ ≤ k ≤ 10⁹.
Think about it: a sliding window fails with negative numbers. Use prefix sums instead: a subarray ending at i has sum k when some earlier prefix equals prefix[i] − k. To make it longest, store only the first index where each prefix sum appears.
Sample input 1
6 3 1 -1 5 -2 3 0
Sample output 1
4
Sample input 2
3 10 1 2 3
Sample output 2
0
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).