Longest Contiguous Subarray with Sum k

Given an array of integers and an integer \( k \), your task is to find the length of the longest contiguous subarray whose elements sum up exactly to \( k \). If no such subarray exists, output 0.

Explanation: You need to identify indices \( i \) and \( j \) (with \( i \le j \)) such that

[ \sum_{l=i}^{j} a_l = k, ]

and the length \( (j-i+1) \) is maximized. This problem can be efficiently solved using prefix sums and a hash table.

inputFormat

The input is read from stdin in the following format:

1. An integer \( n \) representing the number of elements in the array.
2. \( n \) space-separated integers representing the array.
3. An integer \( k \) on a new line.

It is guaranteed that \( n \ge 0 \). For \( n = 0 \), the second line will be empty.

outputFormat

Output a single integer to stdout which is the length of the longest contiguous subarray whose sum is exactly \( k \). If there is no such subarray, output 0.

5
1 2 3 4 5
9

3