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
Prefix sum tracks cumulative totals. - HashMap stores frequency of prefix sums. - If (sum-target) exists, valid subarray found. - Together counts all subarrays with target sum. Conclusion: Demonstrates counting subarrays with given sum using prefix sums.