Subarray Sum Frequencies
MediumPractice library · +20 XPprefix sumshash mapsubarray sums
Given an array of N integers, find the total count of subarrays whose sum is equal to a target value K. A subarray is a contiguous part of the array. You should output a single integer representing this count.
Input
The first line contains two integers N and K, separated by a space. The second line contains N integers representing the array elements, separated by spaces.
Output
A single integer representing the total count of subarrays with sum K.
Constraints
1 <= N <= 200000 -10^9 <= A[i] <= 10^9 -10^15 <= K <= 10^15
Time limit 2 s (native code; slower languages get more)Memory 256 MB15 hidden tests
Example 1
Input
5 3 1 1 1 1 1
Output
3
There are 3 subarrays with sum 3: [1,1,1] starting at index 0, index 1, and index 2.
Example 2
Input
7 0 2 -2 3 -3 1 1 0
Output
6
There are 5 subarrays with sum 0: [-2,2], [3,-3], [-3,3], [0], [2,-2,3,-3].
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 3 1 1 1 1 1
Example 2 input
7 0 2 -2 3 -3 1 1 0