Prefix Sum

Array Sweeps

Signal

Range sums, or subarray sum equals K (with negatives)

Template

Precompute cumulative sums; range = P[j]-P[i]; pair with a hashmap.

Worked example (1)

#4

Prefix Sum

Prefix Sum + Hashmap

Count the number of contiguous subarrays that sum to k. The array may contain negative numbers.

function subarraySum(nums: number[], k: number): number {
  const seen = new Map<number, number>([[0, 1]]); // prefixSum -> count
  let running = 0, count = 0;
  for (const n of nums) {
    running += n;
    count += seen.get(running - k) ?? 0;
    seen.set(running, (seen.get(running) ?? 0) + 1);
  }
  return count;
}

def subarray_sum(nums, k)
  seen = { 0 => 1 } # prefix sum -> how many times seen
  running = 0
  count = 0
  nums.each do |n|
    running += n
    count += seen.fetch(running - k, 0)
    seen[running] = seen.fetch(running, 0) + 1
  end
  count
end