560. Subarray Sum Equals K

Description

The subarraySum function calculates the number of contiguous subarrays within a given array that sum up to a target value k.

Intuition

To efficiently find the number of subarrays with a sum equal to k, we can use a hash map to store the cumulative sums encountered so far and their frequencies. By checking if the difference between the current cumulative sum and the target k exists in the hash map, we can determine the number of valid subarrays ending at the current index.

Approach

1. Initialize a hash map: Create a hash map (cache) to store the cumulative sums and their frequencies. Initialize it with 0 having a frequency of 1 to handle the case where a subarray that sums to k starts from the beginning of the array.
2. Iterate through the array: Maintain a running sum (sum_) of elements. For each element, compute the difference between the current sum and k.
3. Update the count: Check if this difference exists in the hash map. If it does, add the frequency of this difference to the count of valid subarrays.
4. Update the hash map: Increment the frequency of the current cumulative sum in the hash map.
5. Return the count: The count will hold the number of valid subarrays with a sum equal to k.

Complexity

Time Complexity:

O(n), where n is the length of the input array. We iterate through the array once, performing constant-time operations (hash map lookups and updates) for each element.

Space Complexity:

O(n) in the worst case, as we store cumulative sums and their frequencies in the hash map.

Code

C++

class Solution {
public:
    int subarraySum(std::vector& nums, int k) {
        std::unordered_map cache;
        cache[0] = 1;
        int count = 0;
        long sum = 0;

        for (int num : nums) {
            sum += num;
            long diff = sum - k;
            if (cache.find(diff) != cache.end()) {
                count += cache[diff];
            }
            cache[sum]++;
        }

        return count;
    }
};

Python

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        cache = {0: 1}
        count = 0
        sum_ = 0

        for num in nums:
            sum_ += num
            diff = sum_ - k
            if diff in cache:
                count += cache[diff]
            cache[sum_] = cache.get(sum_, 0) + 1

        return count

Java

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map cache = new HashMap<>();
        cache.put(0, 1);
        int count = 0;
        int sum = 0;

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

        return count;
    }
}

JavaScript

var subarraySum = function (nums, k) {
    const cache = new Map();
    cache.set(0, 1);
    let count = 0;
    let sum = 0;
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        let d = sum - k;
        if (cache.has(d)) {
            count += cache.get(d);
        }
        cache.set(sum, (cache.get(sum) ?? 0) + 1);
    }
    return count;
};