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 bolded below:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
Note:
A.length <= 30000
0 <= S <= A.length
A[i] is either 0 or 1.
class Solution:
    def numSubarraysWithSum(self, A: List[int], S: int) -> int:
        numToFreq = {}
        numToFreq[0] = 1
        now_sum = 0
        ans = 0
        for num in A:
            now_sum += num
            if now_sum == S:
                ans += (numToFreq[0])
            elif now_sum > S:
                if now_sum - S in numToFreq:
                    ans += (numToFreq[now_sum - S])
            
            if now_sum not in numToFreq:
                numToFreq[now_sum] = 0
            numToFreq[now_sum] += 1
        return ans
class Solution:
    def numSubarraysWithSum(self, A: List[int], S: int) -> int:
        numToFreq = {}
        numToFreq[0] = 1
        now_sum = 0
        ans = 0
        for num in A:
            now_sum += num
            if now_sum == S:
                ans += (numToFreq[0])
            elif now_sum > S:
                if now_sum - S in numToFreq:
                    ans += (numToFreq[now_sum - S])
            
            if now_sum not in numToFreq:
                numToFreq[now_sum] = 0
            numToFreq[now_sum] += 1
        return ans