Subarray Sum Equals K

Examples

Input: nums = [1, 1, 1], k = 2
Output: 2

The subarray made of the first two elements, and the subarray made of the last two elements, both sum to 2.

Input: nums = [1, 2, 3], k = 3
Output: 2

The subarrays [1, 2] and [3] both sum to 3.

Input: nums = [1, -1, 0], k = 0
Output: 3

[1, -1], [0], and [1, -1, 0] all sum to 0.

Constraints

• 1 <= nums.length <= 2 * 10^4

• -1000 <= nums[i] <= 1000

• -10^7 <= k <= 10^7

Approach

The brute-force way is to check every possible subarray directly, adding up its elements and comparing the sum to k. It works, but it recomputes a lot of the same sums over and over as the window slides.

The faster approach relies on prefix sums: the sum of any subarray between two positions is just the running total up to the later position minus the running total up to the earlier one. So, while scanning the list and keeping a running total, you can ask at every step: "has the running total minus k shown up as a running total before?" A hash map counting how many times each running total has occurred answers that in one step, turning the whole problem into a single pass through the list.

Solutions

Brute Force - Check Every Subarray

For every starting position, extend the subarray one element at a time, keeping a running sum, and count it whenever that running sum equals k.

function subarraySum(nums, k) {
  let count = 0;

  for (let start = 0; start < nums.length; start++) {
    let sum = 0;
    for (let end = start; end < nums.length; end++) {
      sum += nums[end];
      if (sum === k) {
        count++;
      }
    }
  }

  return count;
}

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

Optimal - Prefix Sum + Hash Map

Keep a running total as you scan the list, and a hash map counting how many times each running total value has occurred so far (starting with a running total of 0 having occurred once, to correctly handle subarrays starting at index 0). At each step, the number of subarrays ending here that sum to k equals how many times (current running total minus k) has appeared before.

function subarraySum(nums, k) {
  const prefixCounts = new Map();
  prefixCounts.set(0, 1); // an empty prefix sums to 0

  let sum = 0;
  let count = 0;

  for (const num of nums) {
    sum += num;

    const needed = sum - k;
    if (prefixCounts.has(needed)) {
      count += prefixCounts.get(needed);
    }

    prefixCounts.set(sum, (prefixCounts.get(sum) || 0) + 1);
  }

  return count;
}

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