#127

Subarray Sum Equals K

medium

arrayhash-tableprefix-sum

Given an integer array nums and an integer k, return the total number of contiguous subarrays whose elements sum to exactly k.

The array may contain negative numbers and zeros, so you can't rely on a sliding window — a longer subarray isn't guaranteed to have a larger sum.

Example

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

Output: 2

[1,1] at indices 0..1 and 1..2.

Constraints

1 <= nums.length <= 2 * 10^4
-1000 <= nums[i] <= 1000
-10^7 <= k <= 10^7

Intuition

The most direct approach fixes a start index, then extends an end index, tracking the running sum of that window and counting every time it equals k. Two nested loops cover all O(n²) contiguous subarrays.

function subarraySum(nums, k) {
  let count = 0;
  // Fix each start index...
  for (let start = 0; start < nums.length; start++) {
    let sum = 0;
    // ...and extend the end, accumulating as we go.
    for (let end = start; end < nums.length; end++) {
      sum += nums[end];
      if (sum === k) count++; // this contiguous block hits k
    }
  }
  return count;
}

Brute force — every start/end pair, count the windows summing to k: O(n²).

This is O(n²), and a sliding-window|sliding window can't rescue it: nums may contain negatives, so extending the window can lower the sum — there's no monotonic shrink rule. Can we still do better?

The key observation reuses prefix sums: let prefix be the running sum up to the current index. A subarray ending here sums to k exactly when some earlier prefix equals prefix − k, because subtracting that earlier prefix leaves a contiguous block summing to k. So instead of searching for the start, we ask: how many earlier prefixes had the value `prefix − k`?

Counting occurrences of a value in O(1) is what a Hash map does. Keep a map of prefix value → times seen, seeded with {0: 1} so a subarray starting at index 0 counts itself. At each element add count[prefix − k] to the answer, then record the current prefix. One pass, O(n).

(The stored solution carries the running total in a variable named `prefix` and the map in `counts`.)

Walking it through:

nums = [1, 2, 1, 2, 1], k = 3 · running prefix + counts {0:1}

i↓

prefix = 1 · need 1−3 = −2 (absent) → +0

No earlier prefix is −2, so nothing ends here at sum 3. Record prefix 1. counts = {0:1, 1:1}.

i↓

prefix = 3 · need 3−3 = 0 (seen ×1) → +1

Seeded prefix 0 means the block [1,2] sums to 3. total = 1. Record 3.

i↓

prefix = 4 · need 4−3 = 1 (seen ×1) → +1

Earlier prefix 1 (after index 0) means [2,1] sums to 3. total = 2. Record 4.

i↓

prefix = 6 · need 6−3 = 3 (seen ×1) → +1

Earlier prefix 3 means [1,2] (indices 2–3) sums to 3. total = 3. Record 6.

i↓

prefix = 7 · need 7−3 = 4 (seen ×1) → +1

Earlier prefix 4 means [2,1] (indices 3–4) sums to 3. total = 4. Sweep done.

Optimization

Prefix sums + hash map

Let prefix be the running sum of nums up to the current index. A subarray ending at the current index sums to k exactly when some earlier prefix equals prefix - k — because subtracting that earlier prefix leaves a contiguous block summing to k.

Keep a map of prefix value → how many times it has occurred (seeded with {0: 1} so a subarray that starts at index 0 is counted). At each step, add count[prefix - k] to the answer, then record the current prefix. One pass, O(n) time.

function subarraySum(nums, k) {
  // How many times each running-sum value has been seen; {0:1} lets a
  // subarray starting at index 0 count itself.
  const counts = new Map([[0, 1]]);
  let prefix = 0;
  let total = 0;
  for (const num of nums) {
    prefix += num;
    // Any earlier prefix equal to (prefix - k) closes a subarray summing to k.
    total += counts.get(prefix - k) ?? 0;
    // Record this prefix for subarrays that end later.
    counts.set(prefix, (counts.get(prefix) ?? 0) + 1);
  }
  return total;
}

Complexity analysis

Time complexity: O(n). Here's why:

The algorithm makes a single pass over nums.
Each step does O(1) work: one map lookup for prefix - k and one map insert.

So the whole scan is n × O(1) = O(n) — a clean linear pass, down from the brute force's O(n²) of trying every start/end pair.

Space complexity: O(n). Here's why:

The counts map can hold up to one entry per distinct prefix value, and there are at most n + 1 prefixes — O(n).

The worst case (all distinct prefixes) keeps every prefix in the map, so the extra space is O(n). There's no output array — the answer is a single count.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
nums = [1], k = 1	1	Single element equal to k — one subarray.
nums = [1], k = 2	0	Single element, no subarray sums to k.
nums = [0,0,0,0], k = 0	10	All zeros, k = 0 — every subarray qualifies: 4·5/2 = 10.
nums = [-2,1,1,-2], k = 0	2	Negatives and a zero-sum target: [-2,1,1] and [1,1,-2].
nums = [3,3,3], k = 3	3	Repeated value — each single 3 counts once.
nums = [2,-2,2,-2], k = 0	4	Alternating signs; multiple revisited prefixes.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor