mediumHashingPattern: Prefix Sum + Hash Map
Subarray Sum Counter Solution
Problem Statement
Given an array of integers `arr` and an integer `target`, count the number of contiguous subarrays with a sum equal to `target`.
Examples
Example 1:
Input:{"logs":[1,2,3,4,5],"K":5}
Output:2
Explanation: There are two contiguous sub-logs with a total sum exactly equal to 5: [2, 3] and [5]
Constraints
- 1 <= n <= 2 * 10^4
- -1000 <= arr[i] <= 1000
Time: O(N) Space: O(N)
Use a HashMap to store (prefixSum, frequency). While iterating, calculate current prefixSum. Check if (prefixSum - k) exists in HashMap. If yes, add its frequency to total count. Time O(N), Space O(N).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.