Subarray Sum Counter — Problem Statement & Solution Guide
Problem Description
Given an array of integers nums and an integer target, count the number of contiguous subarrays with a sum equal to target. The function should return the count of such subarrays. Note: The solution should handle the case when the target sum is greater than the maximum possible sum of the subarray, which can cause an overflow error.
Examples
Input
[1, 1, 1, 1, 5]
Output
0
Explanation: Step-by-step: Given the array [1, 1, 1, 1, 5], we need to find the number of contiguous subarrays with a sum equal to 5. However, there is no such subarray in the given array, so the output should be 0.
Input
[1, 2, 3, 4, 5]
Output
0
Explanation: Step-by-step: Given the array [1, 2, 3, 4, 5], we need to find the number of contiguous subarrays with a sum equal to 5. However, the sum of the subarray [1, 2, 3, 4, 5] is 15, not 5, so the output should be 0.
Constraints
- 1 <= n <= 2 * 10^4
- -1000 <= arr[i] <= 1000
Optimal Approach & Strategy
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).
Brute Force Approach
Check all possible subarrays using two nested loops. Time O(N^2).
Verified Code Solutions
var subarraySum = function(nums, k) { let count = 0, sum = 0; let map = new Map(); map.set(0,1); for (let i = 0; i < nums.length; i++) { sum += nums[i]; if (map.has(sum - k)) { count += map.get(sum - k); } map.set(sum, (map.get(sum) || 0) + 1); } return count; }class Solution {
public int subarraySum(int[] nums, int target) {
int count = 0;
int prefix_sum = 0;
Map<Integer, Integer> sum_count = new HashMap<>();
sum_count.put(0, 1);
for (int num : nums) {
prefix_sum += num;
count += sum_count.getOrDefault(prefix_sum - target, 0);
sum_count.put(prefix_sum, sum_count.getOrDefault(prefix_sum, 0) + 1);
}
return count;
}
}def subarraySum(nums, target):
count = 0
prefix_sum = 0
sum_count = {0: 1}
for num in nums:
prefix_sum += num
count += sum_count.get(prefix_sum - target, 0)
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
return countvar subarraySum = function(nums, k) { let count = 0, sum = 0; let map = new Map(); map.set(0,1); for (let i = 0; i < nums.length; i++) { sum += nums[i]; if (map.has(sum - k)) { count += map.get(sum - k); } map.set(sum, (map.get(sum) || 0) + 1); } return count; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.