Sponsored
Sponsored
The prefix sum approach maintains a running sum and stores it in a hash map to efficiently count subarrays with a given sum. By keeping track of the number of times a particular sum has occurred, this method can determine how many subarrays sum to the desired goal by examining previous prefix sums. This solution is highly efficient as it leverages a linear pass through the array.
Time Complexity: O(N) where N is the length of the array.
Space Complexity: O(N) for storing prefix sums.
1function numSubarraysWithSum(nums, goal) {
2 let prefixSumCount = new Map();
3 prefixSumCount.set(0, 1);
4 let currSum = 0;
5 let count = 0;
6 for (let num of nums) {
7 currSum += num;
8 count += prefixSumCount.get(currSum - goal) || 0;
9 prefixSumCount.set(currSum, (prefixSumCount.get(currSum) || 0) + 1);
10 }
11 return count;
12}This JavaScript solution mirrors the Python solution, using a Map to handle prefix sums. As we iterate through nums, we add to the currSum, check for currSum - goal in the map, and update the count as needed.
The sliding window technique incrementally builds a window of elements and checks if its sum matches the goal. Upon reaching or exceeding the goal sum, the window is adjusted by moving the left boundary to find more subarrays that might sum to the goal. This approach is useful for fixed-sum searches without repetitive recalculations.
Time Complexity: O(N) where N is the length of the array.
Space Complexity: O(1) because no additional data structures are used.
1public int numSubarraysWithSum(int[] nums, int goalThis Java implementation uses two pointers to define a sliding window. It increments the end pointer to expand the window until the sum exceeds the goal, then adjusts by incrementing start. It checks for additional valid subarrays by traversing zeros past start.