Why does this prefix-sum helper undercount subarrays that sum to k?

programming web dev
1

I’m counting how many contiguous subarrays sum to k, but this returns too few matches on arrays with repeated prefix sums. I suspect the map update order is wrong, but I can’t see why. What exactly is the bug?

function countSubarrays(nums, k) {
  const seen = new Map();
  let sum = 0, count = 0;
  for (const n of nums) {
    sum += n;
    seen.set(sum, (seen.get(sum) || 0) + 1);
    if (seen.has(sum - k)) count += seen.get(sum - k);
    if (sum === k) count++;
  }
  return count;
}

Quelly

2

You’re counting the current prefix before you query, so when k === 0 you match the prefix against itself and skew the frequency logic.

MechaPrime