Subarray Sum Equals K

Problem Description

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.

Examples

Constraints

• 1 <= nums.length <= 2 * 10⁴
• -1000 <= nums[i] <= 1000
• -10⁷ <= k <= 10⁷

Hashing Prefix Sums to Detect Subarrays

If the sum of elements from index 0 to j is S_j, and the sum from 0 to i (where i < j) is S_i, the sum of the subarray from i+1 to j is S_j - S_i. To find a subarray summing to k, we want S_j - S_i = k, which rewrites as S_i = S_j - k. By iterating through the array and keeping track of the cumulative prefix sum S_j, we check a hash map to see how many times a prefix sum equal to S_j - k has been seen. This allows us to find and count matches in a single pass.

Solution 1: Prefix Sum with Hash Map

Store frequencies of prefix sums in a hash map to count valid subarrays in O(n) time.

import java.util.HashMap;

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int sum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1); // Base case: prefix sum of 0 has occurred once

        for (int num : nums) {
            sum += num;
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}

class Solution:
    def subarraySum(self, nums: list[int], k: int) -> int:
        count = 0
        curr_sum = 0
        prefix_sums = {0: 1}  # Base case: prefix sum of 0 has occurred once
        
        for num in nums:
            curr_sum += num
            if curr_sum - k in prefix_sums:
                count += prefix_sums[curr_sum - k]
            prefix_sums[curr_sum] = prefix_sums.get(curr_sum, 0) + 1
            
        return count

#include <vector>
#include <unordered_map>

class Solution {
public:
    int subarraySum(std::vector<int>& nums, int k) {
        int count = 0;
        int sum = 0;
        std::unordered_map<int, int> prefix_sums;
        prefix_sums[0] = 1; // Base case: prefix sum of 0 has occurred once

        for (int num : nums) {
            sum += num;
            if (prefix_sums.count(sum - k)) {
                count += prefix_sums[sum - k];
            }
            prefix_sums[sum]++;
        }
        return count;
    }
};

Complexity Analysis

• Time Complexity: O(n) since we iterate through the array once and perform O(1) hash map operations.
• Space Complexity: O(n) auxiliary space to store prefix sum occurrences in the hash map.

Where It Breaks

If the array size is extremely large and fits in external storage, storing all prefix sums in memory becomes a bottleneck. However, this is standard for memory bounds on LeetCode questions.

Common Mistakes

• Forgetting the base case: Omitting map.put(0, 1). If a subarray starting at index 0 sums exactly to k, the difference sum - k will be 0. Without the base case entry, this subarray will not be counted.
• Adding the current sum to the map first: Updating the hash map with the current prefix sum before checking for sum - k. If k = 0, this counts the empty subarray starting at the current element, which is incorrect.

Frequently Asked Questions

Why can’t we use a sliding window? Sliding window approaches require that elements are strictly non-negative, ensuring that expanding the window always increases the sum and shrinking it decreases the sum. Since the array can contain negative numbers, the sum is not monotonic, and a sliding window will fail.

What does the hash map record? It records how many times each specific cumulative sum has occurred from the start of the array up to the current position.

← All Problems