Subarray Sum Equals k

You are given an integer array nums and an integer k. Your task is to find the total number of continuous subarrays whose sum equals to k. A subarray is a contiguous part of the array.

For instance, given nums = [1, 1, 1] and k = 2, there are exactly 2 subarrays ([1, 1] from index 0 to 1 and [1, 1] from index 1 to 2) whose sum equals 2.

Mathematically, for an array nums of size n, you need to count the number of pairs of indices \( (i, j) \) satisfying \( 0 \le i \le j < n \) such that:

[ \sum_{t=i}^{j} nums[t] = k ]

Implement an efficient solution with expected time complexity of \( O(n) \) using appropriate data structures (such as hash maps) to handle large input sizes.

inputFormat

The input is read from stdin and consists of three lines:

• 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 nums.
• The third line contains a single integer k, the target sum.

outputFormat

Output to stdout a single integer, which is the total number of continuous subarrays whose sum equals k.

3
1 1 1
2

2