The orignal question can be found here.
The question is asking the number of subarrays which the sum value equals to K. The brute force solution is very straight forward. We simply enumerate all the possible subarrays to find out the total number of subarrays with sum equals K.
The optimal sulution will be leveraging the idea from prefix sum. If you are not familiar with topic, please visit my other post here.
Let’s look at an example for better understanding.
nums: [1,2,3] k=3
prefix_sum: [0,1,3,6]When we iterate to element 2 (index 1), and current prefix sum is 3, we found that there’s already a prefix 0 before, so we know there is a subarray with sum equals 3. When we iterate to element 3 (index 2), the prefix sum is 6, and we found there’s a prefix sum 3 seen before, so we’ve found another one.
However, the question is: what if there are multiple same prefix sum values? Let’s say the nums array is: [1, 2, 0, 3]prefix sum is [0, 1, 3, 3, 6], we know that both [0, 3] and [3] are valid subarrays, so we’ll add 2 to final counter result. But still, every time we calculate a new prefix sum value, we have to loop through the prefix_sum array which hurts the performance. So in this case, we can leverage a hash table (or dictionary in Python) to improve the performance. In this hash table, key is prefix sum, and value is number of occurence of this prefix sum. The code is as following:
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
prefix_sum = {0 : 1}
curr_sum, counter = 0, 0
for num in nums:
curr_sum += num
if curr_sum - k in prefix_sum:
counter += prefix_sum[curr_sum - k]
prefix_sum[curr_sum] = prefix_sum.get(curr_sum, 0) + 1
return counterTime complexity: O(n). Space complexity: O(n)