560. Subarray Sum Equals K

class Solution:
    def subarraySum(self, A: List[int], k: int) -> int:
        """tc O(N) sc O(N)
        main idea: two sum  + prefix sum (psum[i] - psum[j-1] = k => psum[i] - k  = psum[j-1], where j < i =>  count occurance of psum by far and check number of 
        time that psum[i] - k occurred before  => we can use one variable instead of array to reduce the space 
        )
        Note, you may be tempted to try a sliding window here, but the problem is we can have negative numbers
        => so use hash table to save presum instead 
        """
        cnt = psum = 0
        d = {0:1}
        for i in range(len(A)):
            psum += A[i]
            if psum - k  in d:
                cnt += d[psum - k]
            d[psum] = d.get(psum, 0) + 1 
        return cnt