Dare2Solve
The subarraySum
function calculates the number of contiguous subarrays within a given array that sum up to a target value k
.
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.
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.sum_
) of elements. For each element, compute the difference between the current sum and k
.k
.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.
O(n) in the worst case, as we store cumulative sums and their frequencies in the hash map.
class Solution {
public:
int subarraySum(std::vector<int>& nums, int k) {
std::unordered_map<long, int> 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;
}
};
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
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> 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;
}
}
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;
};