Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution:
- def subarraySum(self, nums: List[int], k: int) -> int:
- from collections import defaultdict
- prefixSumCounter = defaultdict(int)
- running_sum = 0
- count = 0
- for num in nums:
- running_sum += num
- # This would be so wrong because if k = 0, you would be double counting
- # prefixSumCounter[running_sum] += 1
- if running_sum == k:
- count += 1
- if running_sum - k in prefixSumCounter:
- # prefix_sum[running_sum - k] gives the number of times the sum running_sum - k has occurred
- # before reaching the current index j.So what we are trying to find how many such j's such that
- # prefixSums has value = running_sum - k
- # by this you are counting all subarry ending at this index but but but you want to exclude
- # counting of prefix sums in it because that is something you are already doing.
- count += prefixSumCounter[running_sum - k]
- # You ensure that only previously encountered prefixSums are considered when checking for (running_sum - k)
- prefixSumCounter[running_sum] += 1
- return count
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement