Subarray Sum Equals Target

Given an array of integers and an integer target k, your task is to compute the number of contiguous subarrays whose sum equals k. A subarray is a contiguous segment of the array.

For instance, for the array [1, 1, 1] with k = 2, there are 2 subarrays that sum to 2. Your solution should be efficient, ideally running in O(n) time, as the array size can be large and the integers can be negative or positive.

Note: The input will be taken from standard input (stdin) and the result should be printed to standard output (stdout).

inputFormat

The input consists of three lines:

1. An integer n representing the number of elements in the array.
2. n space-separated integers representing the array elements. If n is 0, this line will be empty.
3. An integer k representing the target sum.

outputFormat

Output a single integer, the number of contiguous subarrays that sum to k.

3
1 1 1
2

2