Count Contiguous Subarrays with Given Sum

Given an array of integers and a target sum (k), your task is to determine the number of contiguous subarrays whose elements sum to (k).

A subarray is a continuous portion of the array. For instance, if the array is [1, 1, 1] and (k=2), there are two subarrays ([1, 1] starting at index 0 and [1, 1] starting at index 1) whose sum equals 2.

An efficient approach to solve this problem involves the use of prefix sums and hash maps. The idea is to compute the cumulative sum while traversing the array, and look up how many times the cumulative sum (s - k) has occurred before, where (s) is the current cumulative sum. This method achieves an optimal time complexity.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains a single integer (n) representing the number of elements in the array.
  
• The second line contains (n) space-separated integers representing the elements of the array.
  
• The third line contains an integer (k), the target sum.

outputFormat

Output a single integer on standard output (stdout), which is the number of contiguous subarrays that sum to (k).## sample

3
1 1 1
2

2