Count Subarrays with Given Sum
This program counts the number of subarrays with a given sum.
Problem Statement
Write a Java program to count subarrays with sum equal to 7.
Source Code
| 1 | import java.util.HashMap; |
| 2 | public class CountSubarraysGivenSum { |
| 3 | public static void main(String[] args) { |
| 4 | System.out.println("Eduinq Count Subarrays with Given Sum"); |
| 5 | int[] arr = {3,4,7,2,-3,1,4,2}; |
| 6 | int target=7, sum=0, count=0; |
| 7 | HashMap<Integer,Integer> map = new HashMap<>(); |
| 8 | map.put(0,1); |
| 9 | for(int num:arr){ |
| 10 | sum+=num; |
| 11 | if(map.containsKey(sum-target)) count+=map.get(sum-target); |
| 12 | map.put(sum,map.getOrDefault(sum,0)+1); |
| 13 | } |
| 14 | System.out.println("Total subarrays with sum "+target+" = "+count); |
| 15 | } |
| 16 | } |
Program Output
Eduinq Count Subarrays with Given Sum Total subarrays with sum 7 = 4
Explanation
A prefix sum tracks cumulative totals while a HashMap stores the frequency of each prefix sum seen so far, and whenever (sum-target) exists in the map, that many valid subarrays are found, together counting all subarrays with the target sum.