//count all subarrays with sum equals to k using hashmap
import java.util.*;
 
class Ideone {
    public static void main (String[] args) throws java.lang.Exception {
        Scanner sc = new Scanner(System.in);
 
        int[] arr = {1, 2, 3, -3, -1, 4, 5};
        int n = arr.length;
 
        int k = 5;
 
        Map<Integer, Integer> prefixSumCount = new HashMap<>();
        prefixSumCount.put(0, 1);  
 
        int count = 0;
        int sum = 0;
 
        for (int i = 0; i < n; i++) {
            sum += arr[i];
 
            if (prefixSumCount.containsKey(sum - k)) {
                count += prefixSumCount.get(sum - k);
            }
 
            prefixSumCount.put(sum, prefixSumCount.getOrDefault(sum, 0) + 1);
        }
 
        System.out.println("Number of subarrays with sum " + k + ": " + count);
    }
}
 

Ly9jb3VudCBhbGwgc3ViYXJyYXlzIHdpdGggc3VtIGVxdWFscyB0byBrIHVzaW5nIGhhc2htYXAKaW1wb3J0IGphdmEudXRpbC4qOwoKY2xhc3MgSWRlb25lIHsKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbiB7CiAgICAgICAgU2Nhbm5lciBzYyA9IG5ldyBTY2FubmVyKFN5c3RlbS5pbik7CiAgICAgICAgCiAgICAgICAgaW50W10gYXJyID0gezEsIDIsIDMsIC0zLCAtMSwgNCwgNX07CiAgICAgICAgaW50IG4gPSBhcnIubGVuZ3RoOwoKICAgICAgICBpbnQgayA9IDU7CgogICAgICAgIE1hcDxJbnRlZ2VyLCBJbnRlZ2VyPiBwcmVmaXhTdW1Db3VudCA9IG5ldyBIYXNoTWFwPD4oKTsKICAgICAgICBwcmVmaXhTdW1Db3VudC5wdXQoMCwgMSk7ICAKCiAgICAgICAgaW50IGNvdW50ID0gMDsKICAgICAgICBpbnQgc3VtID0gMDsKCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgICAgICAgICAgc3VtICs9IGFycltpXTsKCiAgICAgICAgICAgIGlmIChwcmVmaXhTdW1Db3VudC5jb250YWluc0tleShzdW0gLSBrKSkgewogICAgICAgICAgICAgICAgY291bnQgKz0gcHJlZml4U3VtQ291bnQuZ2V0KHN1bSAtIGspOwogICAgICAgICAgICB9CgogICAgICAgICAgICBwcmVmaXhTdW1Db3VudC5wdXQoc3VtLCBwcmVmaXhTdW1Db3VudC5nZXRPckRlZmF1bHQoc3VtLCAwKSArIDEpOwogICAgICAgIH0KCiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJOdW1iZXIgb2Ygc3ViYXJyYXlzIHdpdGggc3VtICIgKyBrICsgIjogIiArIGNvdW50KTsKICAgIH0KfQo=

NQ==

5