Binary_930.java

import java.util.*;

public class Binary_930 {
    // Standard solution 3: Three Pointers
    public int numSubarraysWithSum(int[] A, int S) {
        int iLo = 0, iHi = 0;
        int sumLo = 0, sumHi = 0;
        int ans = 0;

        for (int j = 0; j < A.length; ++j) {
            // While sumLo is too big, iLo++
            sumLo += A[j];
            while (iLo < j && sumLo > S) sumLo -= A[iLo++];

            // While sumHi is too big, or equal and we can move, iHi++
            sumHi += A[j];
            while (iHi < j && (sumHi > S || sumHi == S && A[iHi] == 0)) sumHi -= A[iHi++];

            if (sumLo == S) ans += iHi - iLo + 1;
        }

        return ans;
    }


    // Standard solution 2: Prefix Sums
    /*
    public int numSubarraysWithSum(int[] A, int S) {
        int N = A.length;
        int[] P = new int[N + 1];
        for (int i = 0; i < N; ++i)
            P[i+1] = P[i] + A[i];

        Map<Integer, Integer> count = new HashMap();
        int ans = 0;
        for (int x: P) {
            ans += count.getOrDefault(x - S, 0);
            count.put(x, count.getOrDefault(x, 0) + 1);
        }

        return ans;
    }
    */
}