Problem statement

Given an integer array nums and an integer k, return the number of contiguous subarrays whose sum equals k.

Example 1

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

Example 2

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

Constraints

• 1 <= nums.length <= 30
• -50 <= nums[i] <= 50
• -100 <= k <= 100

Hints for Subarray Sum Equals K

1. Hint 1

   A subarray sum is a difference of two prefix sums.

2. Hint 2

   Count how many earlier prefixes equal currentPrefix - k using a hash map.

How to solve Subarray Sum Equals K

A subarray's sum is a difference of two prefix sums: the block (i, j] sums to prefix[j] - prefix[i]. So a subarray ending at j hits k exactly when some earlier prefix equals prefix[j] - k. Keep a running tally of how often each prefix value has occurred and the count falls out in one pass.

Approach

1. Track a running prefix sum and a table counting how many times each prefix value has been seen.
2. Seed the table with one occurrence of prefix 0 — that represents the empty prefix, so subarrays starting at index 0 are counted.
3. For each element, add it to prefix.
4. Add to the answer the number of times prefix - k has already been recorded.
5. Then record the current prefix and continue.

Why it works

Each earlier prefix equal to prefix[j] - k marks a distinct starting point for a subarray ending at j that sums to k, so counting them counts exactly the qualifying subarrays with that endpoint. Summing over all endpoints covers every subarray once. Recording the current prefix after the lookup is what prevents a zero-length subarray from being counted when k is 0.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Seeding prefix 0 with a count of one is essential — without it, subarrays that begin at index 0 are missed.
• Look up before recording the current prefix, or k = 0 counts empty subarrays.
• Values may be negative, so sliding-window shrinking does not apply here; prefix counting is the reason this works anyway.
• Prefix sums go negative, so offset the index if using an array instead of a hash map.

Reference solution

Python

from typing import List

def subarraySum(nums: List[int], k: int) -> int:
    seen = {0: 1}
    total = 0
    count = 0
    for x in nums:
        total += x
        count += seen.get(total - k, 0)
        seen[total] = seen.get(total, 0) + 1
    return count

Java

public static int subarraySum(int[] nums, int k) {
    final int OFFSET = 1600, SIZE = 3201;
    int[] seen = new int[SIZE];
    seen[OFFSET] = 1;
    int prefix = 0, count = 0;
    for (int x : nums) {
        prefix += x;
        int want = prefix - k + OFFSET;
        if (want >= 0 && want < SIZE) count += seen[want];
        seen[prefix + OFFSET]++;
    }
    return count;
}

C++

int subarraySum(vector<int>& nums, int k) {
    const int OFFSET = 1600, SIZE = 3201;
    vector<int> seen(SIZE, 0);
    seen[OFFSET] = 1;
    int prefix = 0, count = 0;
    for (int x : nums) {
        prefix += x;
        int want = prefix - k + OFFSET;
        if (want >= 0 && want < SIZE) count += seen[want];
        seen[prefix + OFFSET]++;
    }
    return count;
}

JavaScript

var subarraySum = function(nums, k) {
    const seen = new Map([[0, 1]]);
    let sum = 0, count = 0;
    for (const x of nums) {
        sum += x;
        count += seen.get(sum - k) || 0;
        seen.set(sum, (seen.get(sum) || 0) + 1);
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium