Contiguous Subarray Sum

Given an array of integers and a target integer \( k \), your task is to determine the number of contiguous subarrays within the array that sum exactly to \( k \). A subarray is a contiguous portion of the array. The efficient solution is expected to leverage cumulative sums and a hash table (or equivalent) to keep track of the sums.

For example, if the array is [1, 1, 1] and \( k = 2 \), the answer is 2, since there are two subarrays that sum to 2: the subarray starting at the first element and the one starting at the second element.

inputFormat

The input is given via standard input (stdin) and consists of three lines. The first line contains an integer ( n ) representing the number of elements in the array. The second line contains ( n ) space-separated integers denoting the elements of the array. The third line contains an integer ( k ), the target sum.

outputFormat

Output a single integer to standard output (stdout) representing the number of contiguous subarrays that sum exactly to ( k ).## sample

3
1 1 1
2

2