Subarrays with sum K
Count the contiguous subarrays whose elements add up to exactly K.
Reported in: HCLTech (memory-based)
Input
First line: N. Second line: N integers (may be negative). Third line: K.
Output
The number of subarrays.
Constraints
1 ≤ N ≤ 10^5.
Example 1
Input:
5
1 2 3 -2 2
3
Output:
4Example 2
Input:
3
1 1 1
2
Output:
2Hint: Use prefix sums and a dictionary counting how often each prefix sum has appeared.