930. Binary Subarrays With Sum.md

930. Binary Subarrays With Sum

Difficulty : Medium

Related Topics : Two Pointers、HashTable

---

In an array A of 0s and 1s, how many non-empty subarrays have sum S?

Example 1:

Input: A = [1,0,1,0,1], S = 2
Output: 4
Explanation: 
The 4 subarrays are below:
[1,0,1]//0-2
[1,0,1,0]//0-3
[0,1,0,1]//1-4
[1,0,1]//2-4

Note:

• A.length <= 30000
• 0 <= S <= A.length
• A[i] is either 0 or 1.

---

Solution

• mine
  • Java
    • Runtime: 4 ms, faster than 57.68%, Memory Usage: 52.3 MB, less than 10.33% of Java online submissions

      // O(N)time
      // O(1)space
      public int numSubarraysWithSum(int[] A, int S) {
          int l = 0, count = 0, res = 0;
          int t = S;
          for(int a : A){
              if(a == 1){
                  count = 0;
              }
              if(S == 0){
                  if(a != 1) count++;
              }else{
                  t -= a;
                  while(t == 0){
                      t += A[l++];   
                      count++;
                  }     
              }
              res += count;
          }
          return res;
      }
      

---

• the most votes
  • Runtime: 4 ms, faster than 57.68%, Memory Usage: 51.9 MB, less than 12.78% of Java online submissions

    // O(N)time
    // O(N)space
    public int numSubarraysWithSum(int[] A, int S) {
        int psum = 0, res = 0, count[] = new int[A.length + 1];
        count[0] = 1;
        for (int i : A) {
            psum += i;
            if (psum >= S)
                res += count[psum - S];
            count[psum]++;
        }
        return res;
    }
    

---

• leetcode solution

  • Prefix sum Runtime: 3 ms, faster than 66.17%, Memory Usage: 51.9 MB, less than 12.78% of Java online submissions

    // O(N)time
    // O(N)space
    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];
    
        int[] count = new int[N + 1 + S];
        int ans = 0;
        for (int x: P) {
            ans += count[x];
            count[x + S] ++;
        }
        return ans;
    }
    

  • Three Pointers Runtime: 4 ms, faster than 57.68%, Memory Usage: 53.2 MB, less than 5.17% of Java online submissions

    // O(N)time
    // O(1)space
    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;
    }
    

---