Subarray sum equals k

Count the contiguous subarrays that add up to k. Prefix sums plus a dictionary, and it works with negatives.

Time O(n)Space O(n)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

If the running sum now is S, any earlier point where the running sum was S - k marks the start of a subarray that adds up to k. Count how often each running sum has occurred.

Code

C++PythonC#

int subarraySum(const vector<int>& a, int k) {
    unordered_map<int, int> count{{0, 1}};
    int sum = 0, result = 0;
    for (int x : a) {
        sum += x;
        if (count.count(sum - k)) result += count[sum - k];
        count[sum]++;
    }
    return result;
}

def subarray_sum(a: list[int], k: int) -> int:
    count = {0: 1}
    total = result = 0
    for x in a:
        total += x
        result += count.get(total - k, 0)
        count[total] = count.get(total, 0) + 1
    return result

public static int SubarraySum(int[] a, int k) {
    var count = new Dictionary<int, int> { [0] = 1 };
    int sum = 0, result = 0;
    foreach (int x in a) {
        sum += x;
        if (count.TryGetValue(sum - k, out int c)) result += c;
        count[sum] = count.GetValueOrDefault(sum) + 1;
    }
    return result;
}

Tips

The entry [0] = 1 counts subarrays that start at index 0.
A sliding window cannot solve this once negative numbers are allowed, because the sum no longer grows with the window.

In the .NET library

GetValueOrDefault(key) returns 0 for a missing int key, so "increment or insert" is one line.