Problem Statement
Describe the prefix sum plus hash map technique to count subarrays with sum equal to K.
Explanation
Maintain a running prefix total. For each index j, you want some i where prefix j minus prefix i equals K. Rearranged, prefix i equals prefix j minus K. Keep a map from prefix value to the number of times you have seen it. Add the count of prefix j minus K to the answer and then record prefix j.
This works with negative and positive numbers and runs in linear time. It replaces nested loops with a single scan and a dictionary.
Code Solution
SolutionRead Only
from collections import defaultdict
def count_subarrays_k(nums, K):
pref, seen, ans = 0, defaultdict(int), 0
seen[0] = 1
for x in nums:
pref += x
ans += seen[pref-K]
seen[pref] += 1
return ans