Subarray Sum Equals K

'''
Brute Force: Maintain a window and keep adding the elements until reach k, increment ans once reach k.reduce one element from the left and keep adding the numbers in the array.But here in problem numbers can be negative too where sliding window fails, the core idea of sliding window is adding one element will increase the window size where removing one element will decrease the window size but with negative numbers it doesn't work.

This solution uses a running prefix sum to keep track of the total sum of elements as we iterate through the array.
We store the frequency of each prefix sum in a hashmap, so we can quickly check how many times a particular sum has appeared.
At each step, if the difference between the current prefix sum and k exists in the hashmap, it means there is a subarray ending at the current index that sums to k.
By adding the frequency of this difference to our answer, we count all valid subarrays efficiently.
This approach ensures we find all subarrays with sum k in a single pass with O(n) time complexity.
cur_sum - k tells us what earlier sum we need. The frequency tells us how many times it happened, and every time it happened is a different starting point, so a different valid subarray.

Trick: make the dict[0]=1 so that if sum from start to ith position comes to target, ans should incremented by 1

'''
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        dict={}
        dict[0]=1
        cur=0
        ans=0
        for i in nums:
            cur+=i
            if dict.get(cur-k,0)!=0:
                ans+=dict.get(cur-k)
            dict[cur]=dict.get(cur,0)+1
        return ans