Subarray Sum Equals K

2 min read
Array
LC-Medium

Oct 21, 2022

3 years ago

LeetCode

Solution

Also look at Range Sum Query Immutable
The idea here is to avoid repeated work
While iterating through each number, keep track of the sums seen so far.
- On subsequent iterations, these sums are prefixes.
- These prefix sums that come before our current index are what we need to ADD to our current number at the current index to get k.
- We're just keeping track of the NUMBER OF TIMES a certain prefix sum has been seen.
- For the pic above, k = 3.
  - At index 4, our current sum is 3.
  - current sum minus k = 3 - 3 = 0
  - 0 is our prefix sum, which in previous iterations was our current sum.
  - We've already seen two instances of prefix sums that added up to 0 (the count is what is important, not the actual numbers themselves)
    - These are [1, -1], AND THEN A BASE CASE. WHICH IS INITIALIZING OUR HASHMAP AS {0 : 1}
      - THIS INDICATES THAT FOR THE SUBARRAY THAT STARTS FROM THE 0TH INDEX, OUR PREFIX IS 0, I.E. NO PREFIX. SO JUST INITIALIZE THE HASHMAP WITH THIS.
- In easier terms:
  - At each point, we're just seeing if from the current subarray, if we can chop of a prefix to get our required sum
  - This is why we store the prefix sums in the dictionary to see how many previous subarrays we saw that we could chop off to get our sum
Whenever a prefix sum was seen, just increment our answer by the count, i.e. number of times it was seen.

Time	Space	Explanation
`O(n)`	`O(n)`

def subarraySum(self, nums: List[int], k: int) -> int: counts = defaultdict(lambda: 0) counts[0] = 1 ans, cur_sum = 0, 0 for num in nums: cur_sum += num prefix_sum = cur_sum - k if prefix_sum in counts: ans += counts[prefix_sum] counts[cur_sum] += 1 return ans