Subarray Sum Equals K

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 count

Explanation:

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.

Comments (0)