228. Subarray Sum Equals K
Medium
Prefix Sum Frequency
Array
Problem
Given an integer array nums and an integer k, return the total number of contiguous non-empty subarrays whose sum equals k.
Examples
Example 1
Input: [1,1,1], 2
Output: 2
Example 2
Input: [1,2,3], 3
Output: 2
Example 3
Input: [1,-1,0], 0
Output: 3
Constraints
� 1 <= nums.length <= 20000
� -1000 <= nums[i] <= 1000
� -10000000 <= k <= 10000000
Hints
?? Maintain a running prefix sum.
?? If prefix - k has occurred before, each occurrence forms a valid subarray ending at the current position.
?? Store prefix-sum frequencies rather than only membership.
Expected Complexity
Time: O(n)
Space: O(n)
Follow-up
Why does a normal sliding window not work when negative values are allowed?
Practice Notes
Attempts: 0
Time spent: 0min
Hints used: 0
JavaScript
00:00
Loading...
Case 1
Case 2
Case 3
Input
[1,1,1], 2Expected
2