Subarray Sums Equals k [PRefix Sum]

560.Subarray Sum Equals K

Array

Prefix Sum

Hash Table

Problem Statement:

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

Example:

Input:

nums = [1,1,1], k = 2

→

Output:

2

Algorithm:

1. Track prefix sums in HashMap
2. For each sum, check (sum - k) exists
3. Update map with current sum
4. Add frequency to count

Complexity:

Time: O(n) | Space: O(n)

Java Solution:

// Presum
public int subarraySum(int[] nums, int k) {
    
    // Map to store prefix sum frequencies
    Map<Integer, Integer> preSum = new HashMap<>();
    preSum.put(0, 1);  // Initialize with 0 sum having frequency 1
    int count = 0;
    int sum = 0;
    
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];  // Calculate current prefix sum
        int diff = sum - k;  // Find complement sum
        
        // If complement exists, add its frequency to count
        if (preSum.containsKey(diff)) 
            count += preSum.get(diff);
        
        // Update prefix sum frequency
        preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
    }
    
    return count; 
}

Python Solution:

def subarraySum(self, nums: List[int], k: int) -> int:
    presum = defaultdict(int)
    presum[0] = 1  # Initialize with zero sum
    curr_sum = 0
    count = 0
    
    for num in nums:
        curr_sum += num
        diff = curr_sum - k
        
        # Add frequency of complement sum
        count += presum[diff]
        
        # Update prefix sum frequency
        presum[curr_sum] += 1
        
    return count

C++ Solution:

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> presum;
        presum[0] = 1;  // Initialize with zero sum
        int curr_sum = 0;
        int count = 0;
        
        for(int num : nums) {
            curr_sum += num;
            int diff = curr_sum - k;
            
            // Add frequency of complement sum
            count += presum[diff];
            
            // Update prefix sum frequency
            presum[curr_sum]++;
        }
        
        return count;
    }
};