Subarray Sum Equals K

How it works

The key insight is that if prefixSum[j] - prefixSum[i] = k, then the subarray from index i+1 to j has sum k. This transforms the problem: for each position, we want to count how many earlier positions have a prefix sum equal to currentPrefixSum - k. A hash map lets us track prefix sum frequencies as we iterate, giving O(1) lookups.

Steps

1. Initialize res = 0, curSum = 0, and a hash map prefixSums with {0: 1} (representing the empty prefix).
2. For each number in the array:
   • Add it to curSum.
   • Compute diff = curSum - k.
   • Add prefixSums[diff] to res (counts subarrays ending here with sum k).
   • Increment prefixSums[curSum] by 1.
3. Return res.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Forgetting to Initialize the Hash Map with Zero

The hash map must start with {0: 1} to handle subarrays that start from index 0. Without this initialization, subarrays where prefixSum == k from the beginning will not be counted.

Attempting to Use Sliding Window

Unlike the product variant, this problem allows negative numbers, which means the running sum is non-monotonic. Sliding window does not work here because shrinking the window might increase or decrease the sum unpredictably. The prefix sum + hash map approach is required.

Updating the Hash Map Before Checking

The order of operations matters. You must first check if curSum - k exists in the hash map, then add curSum to the map. Reversing this order would incorrectly count the current element as a valid "previous" prefix sum, leading to wrong results.

from typing import List

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        res = curSum = 0
        prefixSums = { 0 : 1 }

        for num in nums:
            curSum += num
            diff = curSum - k

            res += prefixSums.get(diff, 0)
            prefixSums[curSum] = 1 + prefixSums.get(curSum, 0)

        return res

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int res = 0, curSum = 0;
        unordered_map<int, int> prefixSums;
        prefixSums[0] = 1;

        for (int num : nums) {
            curSum += num;
            int diff = curSum - k;
            res += prefixSums[diff];
            prefixSums[curSum]++;
        }

        return res;
    }
};