Mid · Prefix sums

Count Subarrays with a Target Sum

Count nonempty contiguous subarrays whose sum equals target. Numbers may be negative or zero. Input values and all sums fit within JavaScript safe integers. Do not mutate input.

Examples

[1, -1, 1], 1 → 3

Compare approaches

Extend every start

Accumulate the sum for every start and end pair.

Time: O(n²) · Space: O(1)

function countSums(nums, target) { let count = 0; for (let i = 0; i < nums.length; i++) { let sum = 0; for (let j = i; j < nums.length; j++) { sum += nums[j]; if (sum === target) count++; } } return count; }

Prefix-frequency map

Every previous prefix equal to currentSum - target defines a matching nonempty subarray. Count before recording the current prefix.

Time: O(n) expected · Space: O(n)

function countSums(nums, target) {
  const frequencies = new Map([[0, 1]]);
  let sum = 0, count = 0;
  for (const n of nums) {
    sum += n;
    count += frequencies.get(sum - target) ?? 0;
    frequencies.set(sum, (frequencies.get(sum) ?? 0) + 1);
  }
  return count;
}

Common traps

A positive-only sliding window fails with negative numbers.
Seed prefix zero once to count subarrays starting at index zero.

Practise in the workspace →