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.
1def numSubarraysWithSum(nums, goal):
2 prefix_sum = {0: 1}
3 curr_sum = 0
4 count = 0
5 for num in nums:
6 curr_sum += num
7 count += prefix_sum.get(curr_sum - goal, 0)
8 prefix_sum[curr_sum] = prefix_sum.get(curr_sum, 0) + 1
9 return countThis solution uses a hash map to store prefix sums. As the array is traversed, the current sum is updated. For each element, it checks if curr_sum - goal exists in the hash map, which indicates a valid subarray sum, and updates the count accordingly.
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.