Example:
Input: nums = [1, 1, 1], k = 2
Output: 2
Explanation: The subarrays [1,1] and [1,1] have sum equals to k.
Input: nums = [1, 2, 3], k = 3
Output: 2
Explanation: The subarrays [1, 2] and [3] have sum equals to k.
Solution:
python
def subarraySum(nums, k):
count = 0
sum_map = {0: 1}
current_sum = 0
for num in nums:
current_sum += num
if current_sum - k in sum_map:
count += sum_map[current_sum - k]
sum_map[current_sum] = sum_map.get(current_sum, 0) + 1
return countExplanation:
The idea is to keep track of the running sum while iterating through the array.
Use a hashmap (sum_map) to store the cumulative sum and the count of occurrences of each sum.
Whenever the difference between the current sum and k is found in sum_map, add the count to the result.
Update sum_map accordingly.
Time Complexity: O(n)
Space Complexity: O(n)
This question tests your understanding of hashmaps and your ability to efficiently solve a problem related to subarrays and their sums.