Subarray Sum Equals K — DSA Visualizer

Problem

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

Example 1

Input: nums = [1,1,1], k = 2

Output: 2

Explanation: Subarrays [1,1] at indices [0..1] and [1..2] both sum to 2.

Constraints: 1 ≤ nums.length ≤ 2×10⁴ | −1000 ≤ nums[i] ≤ 1000 | −10⁷ ≤ k ≤ 10⁷

Arrays

Input: nums[] — current index highlighted

Prefix sums — cumulative sum at each position

HashMap: prefixSum → count

Variables

index i

—

prefixSum

—

count

—

Step Logic

Press ▶ Play or Next Step to begin.

Ready

0 / 0

Select an example above and press Play.

Algorithm

Initialize map={0:1}, sum=0, count=0 (base case: empty prefix)

For each n: sum += n (update running prefix sum)

count += map[sum−k] — subarrays ending here that sum to k

map[sum]++ — record this prefix sum, return count

Time

O(n)

Space

O(n)

Why It Works

If prefixSum[i] - prefixSum[j-1] = k, then the subarray from index j to i sums to k. Rearranging: prefixSum[j-1] = prefixSum[i] - k. By storing all previous prefix sums in a HashMap, we can check in O(1) how many valid starting points exist for each ending index. The base case map.put(0, 1) handles subarrays starting at index 0.