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.

Quick Links to Explore