LC 0560 [M] Subarray Sum Equals K - ALawliet/algorithms GitHub Wiki

https://www.youtube.com/watch?v=N0_816yrFrY

(NOT a recursion/backtracking problem but a hashmap!)

• the TRICK is if prefixsum(j)-prefixsum(i)=k, then there is a difference of k from i to j, so if we previously found key: prefixsum(i,j)-k, then there were value: # of prefixsum subarrays = k up to j
• so store a hash table of prefixsum to frequency that prefixsum occurred
• append prefixsum-k frequency to result if we find it in the hashmap and update prefixsum frequency along the way

T: O(n)
S: O(n)

subarraysum[L..R] = pref[R] - pref[L-1]
pref[R] - pref[L-1] = k
pref[L-1] = pref[R] - k # algebra, we know pref[R] but need to find pref[L-1]
need = pref[R] - k # found a valid subarray = k using pref[L-1]
ans += countPref[need] # count how many times that occurred from then until now
countPref[pref]++

---

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        d = defaultdict(int)
        d[0] = 1
        
        pref = ans = 0
        
        for num in nums:
            pref += num
            ans += d[pref - k]
            d[pref] += 1
            
        return ans

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        prefixsum_to_freq = defaultdict(int)
        prefixsum_to_freq[0] = 1 # there is 1 cont subarray whose sum is 0: the empty list

        count_subarrays = 0
        prefixsum = 0
        
        for num in nums:
            prefixsum += num
            count_subarrays += prefixsum_to_freq[prefixsum-k] # this must come first e.g. for args ([1], 0) we want 0 instead of 1
            prefixsum_to_freq[prefixsum] += 1 # this must come second
            
        return count_subarrays