Subarray Sum Equals K

Given an array of integers and a target k, count how many contiguous subarrays sum to exactly k. The array can contain negative numbers, so a sliding window doesn't work here.

Example

Input: 1 1 1, k = 2 Output: 2 ([1,1] at indices 0-1, and [1,1] at indices 1-2)

Approach

Track a running prefix sum as you scan left to right. If prefixSum - k has been seen before, every one of those earlier positions marks the start of a subarray ending here that sums to exactly k — so a hash map from "prefix sum value" to "how many times seen" turns this into a single O(n) pass. Seed the map with {0: 1} to correctly count subarrays that start at index 0.

Input format

Line 1: the array, space-separated Line 2: k

Print the count.