< 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.