560. 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.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

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

Constraints:

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

Python Solution

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        count = 0
        curr_sum = 0
        sum_map = {0: 1}  # Initialize with 0 sum having count 1
        
        for num in nums:
            curr_sum += num
            
            # If (curr_sum - k) exists in map, add its count
            if curr_sum - k in sum_map:
                count += sum_map[curr_sum - k]
            
            # Add current sum to map or increment its count
            sum_map[curr_sum] = sum_map.get(curr_sum, 0) + 1
        
        return count

Java Solution

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int currSum = 0;
        Map sumMap = new HashMap<>();
        sumMap.put(0, 1);  // Initialize with 0 sum having count 1
        
        for (int num : nums) {
            currSum += num;
            
            // If (currSum - k) exists in map, add its count
            if (sumMap.containsKey(currSum - k)) {
                count += sumMap.get(currSum - k);
            }
            
            // Add current sum to map or increment its count
            sumMap.put(currSum, sumMap.getOrDefault(currSum, 0) + 1);
        }
        
        return count;
    }
}

C++ Solution

class Solution {
public:
    int subarraySum(vector& nums, int k) {
        int count = 0;
        int currSum = 0;
        unordered_map sumMap;
        sumMap[0] = 1;  // Initialize with 0 sum having count 1
        
        for (int num : nums) {
            currSum += num;
            
            // If (currSum - k) exists in map, add its count
            if (sumMap.find(currSum - k) != sumMap.end()) {
                count += sumMap[currSum - k];
            }
            
            // Add current sum to map or increment its count
            sumMap[currSum]++;
        }
        
        return count;
    }
};

JavaScript Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    let count = 0;
    let currSum = 0;
    const sumMap = new Map();
    sumMap.set(0, 1);  // Initialize with 0 sum having count 1
    
    for (const num of nums) {
        currSum += num;
        
        // If (currSum - k) exists in map, add its count
        if (sumMap.has(currSum - k)) {
            count += sumMap.get(currSum - k);
        }
        
        // Add current sum to map or increment its count
        sumMap.set(currSum, (sumMap.get(currSum) || 0) + 1);
    }
    
    return count;
};

C# Solution

public class Solution {
    public int SubarraySum(int[] nums, int k) {
        int count = 0;
        int currSum = 0;
        Dictionary sumMap = new Dictionary();
        sumMap[0] = 1;  // Initialize with 0 sum having count 1
        
        foreach (int num in nums) {
            currSum += num;
            
            // If (currSum - k) exists in map, add its count
            if (sumMap.ContainsKey(currSum - k)) {
                count += sumMap[currSum - k];
            }
            
            // Add current sum to map or increment its count
            if (!sumMap.ContainsKey(currSum)) {
                sumMap[currSum] = 0;
            }
            sumMap[currSum]++;
        }
        
        return count;
    }
}