Count Subarrays with Target Sum
EasyPractice library · +10 XPsliding windowprefix sumshash map
Given an array of N integers and a target integer K, find the total number of contiguous subarrays whose elements sum up to exactly K. A subarray is a contiguous part of an array.
Input
The first line contains two integers N and K, separated by a space. The second line contains N integers, the elements of the array, separated by spaces.
Output
Print a single integer, the count of subarrays that sum to K.
Constraints
1 <= N <= 2000; -10^9 <= elements[i] <= 10^9; -10^9 <= K <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
5 7 1 4 2 0 3
Output
2
Subarrays summing to 7 are [4, 2, 0, 1] (sum=7), [4, 2, 1] (sum=7), [4, 3] (sum=7).
Example 2
Input
3 0 1 -1 1
Output
2
Subarrays summing to 0 are [1, -1] (sum=0) and [-1, 1] (sum=0).
Hints
Similar problems
- Longest Subarray With Sum XMedium
- Longest Subarray with Equal HalvesMedium
- Maximum Sum of a Fixed-Size SubarrayEasy
- Count Non-Negative SubarraysEasy
- Count Subarrays with Equal Prefix SumsMedium
- String with Most Unique CharactersMedium
More topics: Hash Map and Hashing problems, Sliding Window problems, Prefix Sums problems
# 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 7 1 4 2 0 3
Example 2 input
3 0 1 -1 1