Loading...
Loading...
Loading...
The numbers are the daily profit or loss of a store (a loss is negative). Count the subarrays (blocks of consecutive days, at least one day) whose total is exactly K.
longExample 1
Input
3 1 2 3 3
Output
2
The subarrays 1 2 and 3.
Example 2
Input
4 1 -1 1 -1 0
Output
4
1 -1 (twice), -1 1, and the whole array.
Try the problem first. Open one hint at a time.
Let prefix[i] be the sum of the first i numbers. The subarray from a to b has the sum prefix[b] - prefix[a].
So at each step, you need the earlier prefix sums that equal currentPrefix - K. Keep a map from prefix sum to how many times it has appeared.
Start the map with 0 -> 1: the empty prefix before the first number.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor