Subarray Sums with Target Difference
MediumPractice library · +20 XPprefix sumshash mapscounting
Given an array of N integers A, find the number of pairs of indices (i, j) such that 1 <= i <= j <= N and the sum of the subarray A[i..j] equals a given target value K. The indices are 1-based.
Input
The first line contains two integers N and K, separated by space. The second line contains N space-separated integers A_1, A_2, ..., A_N.
Output
Print a single integer: the count of pairs (i, j) satisfying the condition.
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 2 1 2 1
Output
4
Subarrays with sum 3 are: [1,2], [2,1], [1,2], [2,1]. Total 4 pairs.
Example 2
Input
3 0 1 -1 1
Output
2
Subarrays with sum 0 are: [1, -1]. Total 1 pair.
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 2 1 2 1
Example 2 input
3 0 1 -1 1