import java.util.*;
 
public class Main {
    public static int countSubarraysOptimized(int[] arr, int k) {
        Map<Integer, Integer> prefixSumCount = new HashMap<>();
        int sum = 0, count = 0;
 
        prefixSumCount.put(0, 1);
 
        for (int num : arr) {
            sum += num;
 
            if (prefixSumCount.containsKey(sum - k)) {
                count += prefixSumCount.get(sum - k);
            }
 
            prefixSumCount.put(sum, prefixSumCount.getOrDefault(sum, 0) + 1);
        }
 
        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));
    }
}
 

aW1wb3J0IGphdmEudXRpbC4qOwogCnB1YmxpYyBjbGFzcyBNYWluIHsKICAgIHB1YmxpYyBzdGF0aWMgaW50IGNvdW50U3ViYXJyYXlzT3B0aW1pemVkKGludFtdIGFyciwgaW50IGspIHsKICAgICAgICBNYXA8SW50ZWdlciwgSW50ZWdlcj4gcHJlZml4U3VtQ291bnQgPSBuZXcgSGFzaE1hcDw+KCk7CiAgICAgICAgaW50IHN1bSA9IDAsIGNvdW50ID0gMDsKIAogICAgICAgIHByZWZpeFN1bUNvdW50LnB1dCgwLCAxKTsKIAogICAgICAgIGZvciAoaW50IG51bSA6IGFycikgewogICAgICAgICAgICBzdW0gKz0gbnVtOwogCiAgICAgICAgICAgIGlmIChwcmVmaXhTdW1Db3VudC5jb250YWluc0tleShzdW0gLSBrKSkgewogICAgICAgICAgICAgICAgY291bnQgKz0gcHJlZml4U3VtQ291bnQuZ2V0KHN1bSAtIGspOwogICAgICAgICAgICB9CiAKICAgICAgICAgICAgcHJlZml4U3VtQ291bnQucHV0KHN1bSwgcHJlZml4U3VtQ291bnQuZ2V0T3JEZWZhdWx0KHN1bSwgMCkgKyAxKTsKICAgICAgICB9CiAKICAgICAgICByZXR1cm4gY291bnQ7CiAgICB9CiAKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgICAgICBpbnRbXSBhcnIgPSB7MSwgMiwgMywgNCwgNX07CiAgICAgICAgaW50IGsgPSA1OwogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiTnVtYmVyIG9mIHN1YmFycmF5cyB3aXRoIHN1bSAiICsgayArICI6ICIgKyBjb3VudFN1YmFycmF5c09wdGltaXplZChhcnIsIGspKTsKICAgIH0KfQog