Subarray Sum Equals K
Module 12 · Prefix Sum
Problem
Given an integer array nums (values may be negative) and an
integer k, return the number of contiguous subarrays whose sum
equals k.
Examples
Example 1
Input
nums = [1,1,1], k = 2Output2Explanation. [1,1] at 0-1, [1,1] at 1-2
Example 2
Input
nums = [1,2,3], k = 3Output2Explanation. [1,2] and [3]
Example 3
Input
nums = [1,-1,0], k = 0Output3Explanation. [1,-1], [0], [1,-1,0]
Constraints
1 ≤ n ≤ 2·10⁴ · values in ±1000 · can be negative.
Attempt it first
The prefix-sum + hash map lesson built this exact algorithm — this problem is that derivation, asked to be reproduced. The negative-values constraint is the tell: it rules out Module 11's sliding window (which needed non-negativity for its shrink logic) and points straight at the hash-map technique instead.