Advertisement
smj007

Subarray sum equals K

Aug 11th, 2024 (edited)
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.25 KB | None | 0 0
  1. class Solution:
  2.     def subarraySum(self, nums: List[int], k: int) -> int:
  3.  
  4.         from collections import defaultdict
  5.         prefixSumCounter = defaultdict(int)
  6.  
  7.         running_sum = 0
  8.         count = 0
  9.  
  10.         for num in nums:
  11.             running_sum += num
  12.  
  13.             # This would be so wrong because if k = 0, you would be double counting
  14.             # prefixSumCounter[running_sum] += 1
  15.  
  16.             if running_sum == k:
  17.                 count += 1
  18.  
  19.             if running_sum - k in prefixSumCounter:
  20.  
  21.                 # prefix_sum[running_sum - k] gives the number of times the sum running_sum - k has occurred
  22.                 # before reaching the current index j.So what we are trying to find how many such j's such that
  23.                 # prefixSums has value = running_sum - k
  24.                 # by this you are counting all subarry ending at this index but but but you want to exclude
  25.                 # counting of prefix sums in it because that is something you are already doing.
  26.                 count += prefixSumCounter[running_sum - k]
  27.  
  28.             #  You ensure that only previously encountered prefixSums are considered when checking for (running_sum - k)
  29.             prefixSumCounter[running_sum] += 1
  30.  
  31.         return count
  32.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement