Problem Description
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k. A subarray is a contiguous non-empty sequence of elements within an array.
Key Insights
- The problem requires finding contiguous subarrays that sum to a specific value
k. - A prefix sum can help track the cumulative sum of elements while iterating through the array.
- A hash map can efficiently store the frequency of prefix sums encountered, allowing for quick lookups to determine how many times a particular sum has occurred.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Solution
The solution utilizes a prefix sum approach combined with a hash map (dictionary) to count the number of subarrays that equal k. As we iterate through the array, we maintain a running sum (current_sum) of elements. For each element, we check if (current_sum - k) exists in our hash map. If it does, it means there are subarrays ending at the current index that sum up to k. We then update our hash map with the current prefix sum.