# LC 560

--

Goal: Find the numbers of subarrays that sum up to k. Array is an int array and has duplicates and negative numbers.

Intuition:

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.

Algorithm:

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

Code: