1.3 Prefix Sum

Demo: Subarray Sum Equals K — LC 560 (Medium)

Statement (Demo): Given an integer array nums and an integer k, return the number of contiguous subarrays that sum to k. Negative numbers are allowed. Example: nums=[1,1,1], k=2 → 2 | ⚡ n ≤ 2×10⁴, -1000 ≤ nums[i] ≤ 1000

Approach: Keep a running prefix sum. sum[i..j] = k means prefix[j] - prefix[i-1] = k, so ask: how many earlier prefixes equal prefix - k? Store prefix counts in a hashmap. This works with negative numbers, where a sliding window fails.

function subarraySum(nums, k) {
  const seen = new Map([[0, 1]]); // the empty prefix
  let sum = 0,
    count = 0;
  for (const x of nums) {
    sum += x;
    count += seen.get(sum - k) || 0;
    seen.set(sum, (seen.get(sum) || 0) + 1);
  }
  return count;
}

Complexity: Time O(n), Space O(n)