Goal: Find the numbers of subarrays that sum up to k. Array is an int array and has duplicates and negative numbers.
when negative numbers are allowed, then we cannot use the sliding window method because we can’t decide the right boundary of the window. Thus, we need a way to guarantee the windows can be closed. So prefix sum is good approach since prefix[i] — prefix[j] == k is a fix window.
Maintaining a hashmap storing <prefix sum: count>, similar to two sum approach, to check complement.
if prefix_sum_so_far == k: cnt++
if prefix_sum_so_far — k in the hashmap: cnt += hashmap[prefix_sum_so_far — k]
insert prefix_sum_so_far into hashmap