Subarray Sum Equals K

Subarray Sum Equals K looks easy at first. Just count the runs that add up to a number, right? But the trick is doing it in one pass. This question is a favorite because it tests whether you really understand prefix sums. That one idea turns a slow solution into a fast one.

🎯 The Problem

You get an array of numbers and a target number called k, and you count the parts that add up to k. Here are the rules.

• Count how many continuous parts of the array add up to k.
• A continuous part is called a subarray. It is a slice where the elements sit next to each other, with no gaps.
• The numbers can be negative. So you cannot stop early just because a sum got big.

Let us say the array is [1, 1, 1] and k is 2. The slice [1, 1] at the start adds up to 2. The slice [1, 1] at the end also adds up to 2. So the answer is 2.

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

Explanation: nums[0..1] = 1 + 1 = 2, and nums[1..2] = 1 + 1 = 2

Here is a picture of the example. Each box is a number. The two highlighted windows are the subarrays that add up to k.

🐢 Approach 1: Check Every Subarray (Brute Force)

The idea in one line: try every start and end pair and add up the numbers between them.

How it works:

• The outer loop fixes the start.
• The inner loop moves the end forward and keeps a running total.
• Each time the total hits k, add one to the count.

Why it is weak:

• For every start you scan forward to the end.
• That is two nested loops over n items.
• So the time grows as O(n²). Slow on a big array.

Here is the brute-force code for that idea:

def subarray_sum(nums, k):
    count = 0

    for start in range(len(nums)):
        total = 0
        for end in range(start, len(nums)):
            total += nums[end]
            if total == k:
                count += 1

    return count


print(subarray_sum([1, 1, 1], 2))

🚶 Approach 2: Prefix Sum Scan (Better)

The idea in one line: keep a running total from each start so you skip re-adding the same numbers.

What a prefix sum is:

• The running total from the start of the array to a spot is the prefix sum.
• It saves you from adding the same stretch over and over.

How it works:

• The outer loop still fixes the start.
• The inner loop keeps a running total as the end moves forward.
• Each time the running total equals k, add one to the count.

Why it is still not enough:

• You drop the inner re-summing, which is a real saving.
• But you still try every start and end pair.
• So the time is still O(n²). We can do better in one pass.

Here is the prefix-sum scan code for that idea:

def subarray_sum(nums, k):
    prefix = [0]
    for num in nums:
        prefix.append(prefix[-1] + num)

    count = 0
    for start in range(len(nums)):
        for end in range(start + 1, len(nums) + 1):
            if prefix[end] - prefix[start] == k:
                count += 1

    return count


print(subarray_sum([1, 1, 1], 2))

⚡ Approach 3: Prefix Sum With a Hash Map (Best)

The idea in one line: count, in one pass, how many earlier prefix sums equal total - k.

The key insight:

• A subarray ending at a spot sums to the prefix sum there minus the prefix sum just before it started.
• So if the current prefix sum is total, a subarray ending here sums to k when some earlier prefix sum equals total - k.

How it works:

• Store every prefix sum you have seen in a hash map. A hash map stores a key and a count and looks it up almost instantly.
• Walk the array once. Add the current number to total.
• Look up total - k in the map. Add its count to the answer.
• Record the current total in the map.
• Start the map with {0: 1}. That zero stands for the empty prefix, so a subarray that starts at index 0 is counted.

Why it is fast:

• One pass over the array, with near-instant lookups.
• So it runs in O(n) time. The map costs O(n) space.

This picture shows the dry run on [1, 1, 1] with k = 2. Follow the running total and the map.

Steps to Solve

1. Create a hash map that maps a prefix sum to how many times it has appeared. Start it with {0: 1}.
2. Set total to 0 and count to 0.
3. Walk through the array one number at a time. Add the number to total.
4. Look up total - k in the map. Add its stored count to count.
5. Increase the stored count of total in the map by one.
6. After the loop, return count.

#include <stdio.h>
#include <string.h>

#define SIZE 4001  // a prime-ish size for the hash table

int keys[SIZE];
int counts[SIZE];
int used[SIZE];

// find the slot for a prefix-sum key (handles negatives too)
int slotFor(int key) {
    long h = ((long)key % SIZE + SIZE) % SIZE;
    while (used[h] && keys[h] != key) {
        h = (h + 1) % SIZE;  // linear probing
    }
    return (int)h;
}

int subarraySum(int nums[], int n, int k) {
    memset(used, 0, sizeof(used));
    int start = slotFor(0);   // prefix sum 0 seen once (empty prefix)
    keys[start] = 0;
    counts[start] = 1;
    used[start] = 1;

    int total = 0, answer = 0;
    for (int i = 0; i < n; i++) {
        total += nums[i];
        int need = slotFor(total - k);   // prefix sum we are looking for
        if (used[need]) {
            answer += counts[need];
        }
        int self = slotFor(total);       // record current prefix sum
        if (used[self]) {
            counts[self]++;
        } else {
            keys[self] = total;
            counts[self] = 1;
            used[self] = 1;
        }
    }
    return answer;
}

int main(void) {
    int nums[] = {1, 1, 1};
    int k = 2;
    printf("%d\n", subarraySum(nums, 3, k));
    return 0;
}

2

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> seen;  // prefix sum -> how many times seen
    seen[0] = 1;                   // empty prefix
    int total = 0, answer = 0;
    for (int num : nums) {
        total += num;
        if (seen.count(total - k)) {   // a matching earlier prefix exists
            answer += seen[total - k];
        }
        seen[total]++;                 // record this prefix sum
    }
    return answer;
}

int main() {
    vector<int> nums = {1, 1, 1};
    int k = 2;
    cout << subarraySum(nums, k) << endl;
    return 0;
}

2

import java.util.HashMap;
import java.util.Map;

public class SubarraySum {
    public static int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> seen = new HashMap<>();  // prefix sum -> count
        seen.put(0, 1);                                // empty prefix
        int total = 0, answer = 0;
        for (int num : nums) {
            total += num;
            if (seen.containsKey(total - k)) {     // matching earlier prefix
                answer += seen.get(total - k);
            }
            seen.put(total, seen.getOrDefault(total, 0) + 1);  // record prefix
        }
        return answer;
    }

    public static void main(String[] args) {
        int[] nums = { 1, 1, 1 };
        int k = 2;
        System.out.println(subarraySum(nums, k));
    }
}

2

def subarray_sum(nums, k):
    seen = {0: 1}        # prefix sum -> how many times seen (empty prefix)
    total = 0
    answer = 0
    for num in nums:
        total += num                       # running prefix sum
        if (total - k) in seen:            # a matching earlier prefix exists
            answer += seen[total - k]
        seen[total] = seen.get(total, 0) + 1  # record this prefix sum
    return answer


nums = [1, 1, 1]
k = 2
print(subarray_sum(nums, k))

2

function subarraySum(nums, k) {
  const seen = new Map(); // prefix sum -> how many times seen
  seen.set(0, 1);         // empty prefix
  let total = 0;
  let answer = 0;
  for (const num of nums) {
    total += num;                          // running prefix sum
    if (seen.has(total - k)) {             // matching earlier prefix exists
      answer += seen.get(total - k);
    }
    seen.set(total, (seen.get(total) || 0) + 1); // record this prefix sum
  }
  return answer;
}

const nums = [1, 1, 1];
const k = 2;
console.log(subarraySum(nums, k));

2

Let us walk through the Python version line by line. Code first, then the why.

def subarray_sum(nums, k):
    seen = {0: 1}
    total = 0
    answer = 0
    for num in nums:
        total += num
        if (total - k) in seen:
            answer += seen[total - k]
        seen[total] = seen.get(total, 0) + 1
    return answer

seen = {0: 1} starts the map with one prefix sum of zero. This stands for the empty prefix before the array begins. Without it, a subarray that starts at index 0 and sums to k would be missed. So this line is the quiet hero of the whole solution.

total += num updates the running prefix sum. After this line, total holds the sum of every number from the start up to the current one.

if (total - k) in seen: asks the key question. If some earlier prefix sum equals total - k, then the part between that point and here sums to exactly k. We are checking the map, not scanning the array. That is why it is fast.

answer += seen[total - k] adds the count. There may be several earlier positions that share the same prefix sum. Each one gives a valid subarray. So we add all of them, not just one.

seen[total] = seen.get(total, 0) + 1 records the current prefix sum for future steps. We add the current value after the lookup. That order matters. It stops a single element from pairing with itself.

⏱️ Time and Space Complexity

The brute force checks every subarray with two loops, so it is slow but uses almost no extra memory. The prefix sum with a hash map walks the array just once, so it is fast, but it needs extra memory to store the prefix sums it has seen. So you trade a little memory to save a lot of time. That trade takes the time from O(n²) down to O(n).

🧩 Key Takeaways

• ✅ A subarray sum equals the prefix sum at the end minus the prefix sum before it started.
• ✅ For each prefix sum total, look for an earlier prefix sum equal to total - k.
• ✅ Store prefix sums and their counts in a hash map for almost instant lookups.
• ✅ Seed the map with {0: 1} so subarrays that start at index 0 are counted.
• ✅ This works with negative numbers, where a sliding window would fail.

🚀 What’s Next?

• Next Permutation
• Two Sum