Subarray Sum Equals K

Problem Given an integer array nums (values may be negative) and an integer k, count the contiguous subarrays whose sum equals exactly k.

Input / Output

• Input: int array nums, int k. Output: count of subarrays.

Constraints

• n up to 2*10^4 with negatives — sliding window is invalid (no monotonicity); O(n) hashmap expected.

Example

• nums = [1,1,1], k = 2 → 2; nums = [1,-1,0], k = 0 → 3.

Expected approach

• Prefix sum + frequency hashmap: running sum s at index i; subarrays ending at i summing to k correspond to prior prefixes equal to s − k. Count += freq[s−k], then increment freq[s]; seed freq[0] = 1 for subarrays starting at index 0. O(n) time/space. Be ready to explain exactly why negatives kill the two-pointer window — a standard probing question.