Subarray Sum Equals K
The key idea
A subarray
nums[i..j] sums to k exactly when prefix[j] - prefix[i-1] == k, i.e. when an earlier prefix equals prefix[j] - k. So while scanning, keep a running sum and a count of every prefix sum seen so far; at each index add the number of earlier prefixes equal to sum - k. Because nums can be negative, a sliding window does not work — the prefix-sum hash map does.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 the array. Note that nums may contain negative numbers, so a growing window does not necessarily stay below the target.
Constraints
1 <= nums.length <= 2 * 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7
Examples
Input: nums = [1,1,1], k = 2
Output: 2
Input: nums = [1,2,3], k = 3
Output: 2
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization