Subarray Sum Equals K

Difficulty: Medium

Problem

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

Example

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

Brute-force approach

Try every start index and compute sums for every end index.

Steps

1. For each start i, initialize sum = 0
2. For each end j >= i, add nums[j] to sum
3. If sum == k, increment answer

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

• Too slow for large inputs (n can be up to 20,000)
• Repeatedly recomputes overlapping sums

Optimal approach

Key insight: A subarray ending at index j sums to k if there exists a previous prefix sum equal to (currentPrefix - k).

Maintain a running prefix sum and a hash map of how many times each prefix sum has appeared.

Steps

1. Initialize freq[0] = 1 (empty prefix)
2. Scan array, updating prefixSum
3. Add freq[prefixSum - k] to answer
4. Increment freq[prefixSum]

Time complexity: O(n) · Space complexity: O(n)