Loading...
Loading...
Loading...
Given n integers (which may be negative) and a number k, count the non-empty runs of consecutive values whose sum is exactly k. Adding up every run is too slow.
Example
Input
5 3 1 2 1 2 1
Output
4
Try the problem first. Open one hint at a time.
A run from i to j has sum prefix[j] - prefix[i - 1]. Checking all runs is O(n²).
Walk once with a running total. Count how many earlier prefix totals equal total - k, using a Counter that starts with {0: 1}.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor