Subarray Sum Equals K

Problem Statement

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k. A subarray is a contiguous non-empty sequence of elements within an array.

Key insight

• A subarray is contiguous — this is NOT the subset sum problem.
• The key identity: if prefix[j] - prefix[i] == k, then the subarray (i, j] sums to k.
• Initialize the map with {0: 1} to handle subarrays starting at index 0.

Examples

Input	k	Output
[1,1,1]	2	2
[1,2,3]	3	2

Constraints

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

Real-World Applications

Where this pattern appears

• Transaction analysis — count time windows where spend equals a budget exactly.
• Signal processing — count segments where signal energy equals a threshold.
• Game score tracking — count game spans where score delta equals a target.
• Network monitoring — count intervals where bandwidth usage equals a quota.

Complexity Comparison

Approach	Time	Space	Best When
Prefix Sum + Hash Map	O(n)	O(n)	Always — handles negatives too
Brute Force	O(n²)	O(1)	Understanding only

Approach 1: Prefix Sum Hash Map (Recommended)

★ Recommended

Keep a running prefix sum. Use a hash map count[prefix_sum] → occurrences. For each position, check if prefix_sum - k exists in the map — if it does, there are that many subarrays ending here that sum to k. Add the current prefix sum to the map after checking.

⏱ Time O(n) Single pass 💾 Space O(n) Hash map storage

Step-by-step Example

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

i	num	prefix	prefix−k	map (before check)	count added	map (after insert)
—	—	0	—	{}	—	{0:1}
0	1	1	-1	{0:1}	0	{0:1, 1:1}
1	1	2	0	{0:1, 1:1}	1	{0:1, 1:1, 2:1}
2	1	3	1	{0:1, 1:1, 2:1}	1	{0:1, 1:1, 2:1, 3:1}

Result: 2 (subarrays [1,1] at indices 0–1 and 1–2)

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

i	num	prefix	prefix−k	map (before check)	count added
—	—	0	—	{}	—
0	1	1	-2	{0:1}	0
1	2	3	0	{0:1, 1:1}	1
2	3	6	3	{0:1, 1:1, 3:1}	1

Result: 2 (subarrays [1,2] and [3])

Animated walkthrough

Prefix sum hash map counting subarrays

Use Next or Autoplay to watch the running prefix sum, the map lookup, and the result accumulate for nums=[1,1,1], k=2.

Back Autoplay Next Reset

Step 1 of 4

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function subarraySum(nums, k):
    count = {0: 1}
    prefix = 0
    result = 0
    for num in nums:
        prefix += num
        result += count.get(prefix - k, 0)
        count[prefix] = count.get(prefix, 0) + 1
    return result

Solution Code

Python

subarray_sum_equals_k_prefix_sum.py

from typing import List


def subarray_sum_prefix_sum(nums: List[int], k: int) -> int:
    count = {0: 1}
    prefix = 0
    result = 0
    for num in nums:
        prefix += num
        result += count.get(prefix - k, 0)
        count[prefix] = count.get(prefix, 0) + 1
    return result

print(subarray_sum_prefix_sum([1, 1, 1], k=2))  # 2
print(subarray_sum_prefix_sum([1, 2, 3], k=3))  # 2

C++

subarray_sum_equals_k_prefix_sum.cpp

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

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        count[0] = 1;
        int prefix = 0, result = 0;
        for (int num : nums) {
            prefix += num;
            auto it = count.find(prefix - k);
            if (it != count.end()) {
                result += it->second;
            }
            count[prefix]++;
        }
        return result;
    }
};

Java

subarray_sum_equals_k_prefix_sum.java

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

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        count.put(0, 1);
        int prefix = 0, result = 0;
        for (int num : nums) {
            prefix += num;
            result += count.getOrDefault(prefix - k, 0);
            count.put(prefix, count.getOrDefault(prefix, 0) + 1);
        }
        return result;
    }
}

JavaScript

subarray_sum_equals_k_prefix_sum.js

function subarraySum(nums, k) {
    const count = new Map([[0, 1]]);
    let prefix = 0, result = 0;
    for (const num of nums) {
        prefix += num;
        result += count.get(prefix - k) ?? 0;
        count.set(prefix, (count.get(prefix) ?? 0) + 1);
    }
    return result;
}

Rust

subarray_sum_equals_k_prefix_sum.rs

use std::collections::HashMap;

impl Solution {
    pub fn subarray_sum(nums: Vec<i32>, k: i32) -> i32 {
        let mut count: HashMap<i32, i32> = HashMap::new();
        count.insert(0, 1);
        let mut prefix = 0;
        let mut result = 0;
        for num in nums {
            prefix += num;
            result += count.get(&(prefix - k)).copied().unwrap_or(0);
            *count.entry(prefix).or_insert(0) += 1;
        }
        result
    }
}

Go

subarray_sum_equals_k_prefix_sum.go

func subarraySum(nums []int, k int) int {
    count := map[int]int{0: 1}
    prefix, result := 0, 0
    for _, num := range nums {
        prefix += num
        result += count[prefix-k]
        count[prefix]++
    }
    return result
}

Approach 2: Brute Force

✓ Simple

Check every possible subarray using two nested loops. The outer loop picks the start index; the inner loop extends the window right, accumulating the sum. When the running sum equals k, increment the count.

⏱ Time O(n²) All subarrays checked 💾 Space O(1) No extra memory

Step-by-step Example

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

i	j	running sum	== k?
0	0	1	no
0	1	3	yes → count=1
0	2	6	no
1	1	2	no
1	2	5	no
2	2	3	yes → count=2

Result: 2

Pseudocode

function subarraySum(nums, k):
    result = 0
    for i in range(len(nums)):
        total = 0
        for j in range(i, len(nums)):
            total += nums[j]
            if total == k:
                result += 1
    return result

Solution Code

Python

subarray_sum_equals_k_brute_force.py

from typing import List


def subarray_sum_brute_force(nums: List[int], k: int) -> int:
    result = 0
    for i in range(len(nums)):
        total = 0
        for j in range(i, len(nums)):
            total += nums[j]
            if total == k:
                result += 1
    return result

print(subarray_sum_brute_force([1, 1, 1], k=2))  # 2
print(subarray_sum_brute_force([1, 2, 3], k=3))  # 2

C++

subarray_sum_equals_k_brute_force.cpp

#include <vector>
using namespace std;

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int result = 0;
        for (int i = 0; i < (int)nums.size(); i++) {
            int total = 0;
            for (int j = i; j < (int)nums.size(); j++) {
                total += nums[j];
                if (total == k) result++;
            }
        }
        return result;
    }
};

Java

subarray_sum_equals_k_brute_force.java

class Solution {
    public int subarraySum(int[] nums, int k) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            int total = 0;
            for (int j = i; j < nums.length; j++) {
                total += nums[j];
                if (total == k) result++;
            }
        }
        return result;
    }
}

JavaScript

subarray_sum_equals_k_brute_force.js

function subarraySum(nums, k) {
    let result = 0;
    for (let i = 0; i < nums.length; i++) {
        let total = 0;
        for (let j = i; j < nums.length; j++) {
            total += nums[j];
            if (total === k) result++;
        }
    }
    return result;
}

Rust

subarray_sum_equals_k_brute_force.rs

impl Solution {
    pub fn subarray_sum(nums: Vec<i32>, k: i32) -> i32 {
        let mut result = 0;
        for i in 0..nums.len() {
            let mut total = 0;
            for j in i..nums.len() {
                total += nums[j];
                if total == k {
                    result += 1;
                }
            }
        }
        result
    }
}

Go

subarray_sum_equals_k_brute_force.go

func subarraySum(nums []int, k int) int {
    result := 0
    for i := 0; i < len(nums); i++ {
        total := 0
        for j := i; j < len(nums); j++ {
            total += nums[j]
            if total == k {
                result++
            }
        }
    }
    return result
}

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

subarray_sum_equals_k_space_optimized.py

"""
Solution for Subarray Sum Equals K
"""

def solve():
    """Implementation for approach 3 of Subarray Sum Equals K"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

subarray_sum_equals_k_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Subarray Sum Equals K
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

SubarraySumEqualsKSpaceOptimized.java

/**
 * Solution for Subarray Sum Equals K
 * Approach 3
 */
public class SubarraySumEqualsKSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

subarray_sum_equals_k_space_optimized.js

/**
 * Solution for Subarray Sum Equals K
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

subarray_sum_equals_k_space_optimized.rs

/// Solution for Subarray Sum Equals K
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

subarray_sum_equals_k_space_optimized.go

package main

import "fmt"

// Solution for Subarray Sum Equals K
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Common Mistakes

Watch for these pitfalls

• Not initializing the map with {0: 1} — this misses subarrays that start at index 0 (where the prefix sum itself equals k).
• Using a sliding window — this does not work here because nums can contain negatives or zeros. A shrinking window cannot undo the damage of a negative number.
• Updating the map before the lookup — always check count[prefix - k] first, then insert prefix into the map.

Related Problems

• Two Sum ↗ Easy #1
• Contiguous Array ↗ Medium #525
• Product of Array Except Self ↗ Medium #238

Interview Tips

Key points to discuss

• The {0: 1} initialization is the trickiest part — explain that it accounts for subarrays starting at index 0, where the prefix sum itself equals k.
• Why not a sliding window? — the array can contain negative numbers and zeros, so shrinking the window does not reliably reduce the sum. The hash map handles all cases in one pass.
• Follow-up: “What if all numbers are positive?” — then a two-pointer sliding window works and uses O(1) extra space.
• Order of operations matters: check count[prefix - k] before inserting prefix, otherwise a subarray of length zero could be counted.

← Previous
#530 Minimum Absolute Difference in BST Next
#637 Average of Levels in Binary Tree →