Subarray Sum Equals K
Medium · Prefix Sums · Array · Hash Table · Prefix Sum
Problem
Return how many contiguous subarrays of nums sum to exactly k.
Values may be negative, so a running sum does not only increase.
Examples
Input: nums = [1,1,1], k = 2 Output: 2
The two overlapping [1,1] windows both count.
Input: nums = [1,2,3], k = 3 Output: 2
[1,2] and [3].
Constraints
- 1 <= len(nums) <= 2 * 10^4
- -1000 <= nums[i] <= 1000
- -10^7 <= k <= 10^7
Approaches
- Brute force — every subarray — time O(n²), space O(1)
Related problems
Start free on Cariara · Coding problems · System design studio
