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:

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store