Subarray Sum Equals K — Prefix Sum + HashMap O(n) [Google, Meta]

Problem Statement

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

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

Intuition
C++ Solution
Java Solution
Python Solution
JavaScript Solution
Complexity: O(n) time, O(n) space

Intuition

A subarray nums[i..j] has sum k iff prefix[j+1] - prefix[i] = k iff prefix[i] = prefix[j+1] - k.

Use a HashMap counting how many times each prefix sum has appeared.

count = {0: 1}  # prefix sum 0 seen once (empty prefix)
prefix = 0, result = 0
for each num:
    prefix += num
    result += count.get(prefix - k, 0)
    count[prefix] += 1
return result

C++ Solution

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> cnt = {{0,1}};
        int prefix = 0, res = 0;
        for (int n : nums) {
            prefix += n;
            res += cnt.count(prefix-k) ? cnt[prefix-k] : 0;
            cnt[prefix]++;
        }
        return res;
    }
};

Java Solution

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

Python Solution

from collections import defaultdict
def subarraySum(nums, k):
    cnt = defaultdict(int)
    cnt[0] = 1
    prefix = res = 0
    for n in nums:
        prefix += n
        res += cnt[prefix - k]
        cnt[prefix] += 1
    return res

JavaScript Solution

function subarraySum(nums, k) {
    const cnt = new Map([[0, 1]]);
    let prefix = 0, res = 0;
    for (const n of nums) {
        prefix += n;
        res += (cnt.get(prefix - k) || 0);
        cnt.set(prefix, (cnt.get(prefix)||0) + 1);
    }
    return res;
}

Complexity: O(n) time, O(n) space

Important: This works with negative numbers too (unlike sliding window). For only positive numbers, plain sliding window works.