< Back




 560. Subarray Sum Equals K

This one's a bit confusing. So in the past we were finding prefix sums that were fitting a constraint
like being less than some given value k. This enabled us to use a sliding window, and we could shrink
or increase the size of the window from the left until we met the constraint.

In this problem, we're looking for subarrays that sum to k. We need to use a counter or a dictionary
to keep track of the previously seen prefix sums that can be used as starting points in tandem with
the current index to create a prefix sum that sums to k.

Take for instance the empty prefix array []. The sum of this prefix is 0. Eventually we will
encounter a prefix sum where curr - k == 0. Therefore curr - (curr - k) == k. So the difference
between the empty prefix array [] and the current prefix sum is k. This means that if we started a
prefix sum from the end of the empty array to the current index, we would have a subarry that sums to
k.

Because the empty prefix array [] has already been seen, we can use count[curr - k (0)] and add the
value to the result, accounting for a subarray that sums to k defined by the end of the empty prefix
array and the current index.

This same logic applies to any prefix sum encountered in the rest of the list.

The solution is as follows:


  class Solution:
      def subarraySum(self, nums: List[int], k: int) -> int:
          counts = defaultdict(int)
          counts[0] = 1
          ans = curr = 0

          for num in nums:
              curr += num
              ans += counts[curr - k]
              counts[curr] += 1

          return ans


_ Time Complexity:

  O(n) - We iterate through the array once.

_ Space Complexity:

  O(n) - We store at most n keys in the dictionary.