import java.util.*;
 
public class Main {
    public static int countSubarraysOptimized(int[] arr, int k) {
        Map<Integer, Integer> prefixSumCount = new HashMap<>();
        int count = 0;
 
        prefixSumCount.put(0, 1);
        int temp = arr[0];
        for(int i = 0; i<arr.length; i++){
        	temp +=arr[i];
        	prefixSumCount.put(temp, prefixSumCount.getOrDefault(temp, 0) + 1);
        }
 
        for (int key : prefixSumCount.keySet()) {
            if (prefixSumCount.containsKey(key - k)) {
                count += prefixSumCount.get(key - k);
            }
        }
 
        return count;
    }
 
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int k = 5;
        System.out.println("Number of subarrays with sum " + k + ": " + countSubarraysOptimized(arr, k));
    }
}
 

aW1wb3J0IGphdmEudXRpbC4qOwoKcHVibGljIGNsYXNzIE1haW4gewogICAgcHVibGljIHN0YXRpYyBpbnQgY291bnRTdWJhcnJheXNPcHRpbWl6ZWQoaW50W10gYXJyLCBpbnQgaykgewogICAgICAgIE1hcDxJbnRlZ2VyLCBJbnRlZ2VyPiBwcmVmaXhTdW1Db3VudCA9IG5ldyBIYXNoTWFwPD4oKTsKICAgICAgICBpbnQgY291bnQgPSAwOwoKICAgICAgICBwcmVmaXhTdW1Db3VudC5wdXQoMCwgMSk7CiAgICAgICAgaW50IHRlbXAgPSBhcnJbMF07CiAgICAgICAgZm9yKGludCBpID0gMDsgaTxhcnIubGVuZ3RoOyBpKyspewogICAgICAgIAl0ZW1wICs9YXJyW2ldOwogICAgICAgIAlwcmVmaXhTdW1Db3VudC5wdXQodGVtcCwgcHJlZml4U3VtQ291bnQuZ2V0T3JEZWZhdWx0KHRlbXAsIDApICsgMSk7CiAgICAgICAgfQoKICAgICAgICBmb3IgKGludCBrZXkgOiBwcmVmaXhTdW1Db3VudC5rZXlTZXQoKSkgewogICAgICAgICAgICBpZiAocHJlZml4U3VtQ291bnQuY29udGFpbnNLZXkoa2V5IC0gaykpIHsKICAgICAgICAgICAgICAgIGNvdW50ICs9IHByZWZpeFN1bUNvdW50LmdldChrZXkgLSBrKTsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgcmV0dXJuIGNvdW50OwogICAgfQoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgICAgICBpbnRbXSBhcnIgPSB7MSwgMiwgMywgNCwgNX07CiAgICAgICAgaW50IGsgPSA1OwogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiTnVtYmVyIG9mIHN1YmFycmF5cyB3aXRoIHN1bSAiICsgayArICI6ICIgKyBjb3VudFN1YmFycmF5c09wdGltaXplZChhcnIsIGspKTsKICAgIH0KfQo=