🎨Now live: Try our Free AI Image Generation Feature

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
- Initialize a hash map: Create a hash map (
cache
) to store the cumulative sums and their frequencies. Initialize it with0
having a frequency of1
to handle the case where a subarray that sums tok
starts from the beginning of the array. - Iterate through the array: Maintain a running sum (
sum_
) of elements. For each element, compute the difference between the current sum andk
. - 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.
- Update the hash map: Increment the frequency of the current cumulative sum in the hash map.
- 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;
};