Subarray Sum Equals K

Problem

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals k.

A subarray is a contiguous non-empty sequence of elements within an array.

Input / Output Format

Input: Array nums, integer k. Output: Integer — count of subarrays summing to k.

Examples

Example 1

Input: nums = [1,1,1], k = 2 Output: 2 Explanation: Subarrays [1,1] (indices 0-1) and [1,1] (indices 1-2). Both sum to 2.

Example 2

Input: nums = [1,2,3], k = 3 Output: 2 Explanation: [1,2] and [3].

Approach Hints

• Prefix Sum + Hash Map — Maintain running prefixSum. At each index, the number of subarrays ending here that sum to k equals the count of earlier positions where prefix sum equaled prefixSum - k. Use a hash map {prefixSum: count} initialized with {0: 1}.
• Why not sliding window? Array may contain negatives, so sliding window's monotonicity assumption breaks.
• Time: O(n). Space: O(n).