16. Binary Subarrays With Sum

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]

Solution: (Sliding Window)

Similar Approach to the Count Nice Subarrays Edge case: S = 0 Finding the number of zero in between ones and calculation number of sub arrays

class Solution
{
public:
    int numSubarraysWithSum(vector<int> &A, int S)
    {

        vector<int> v;
        v.push_back(-1);

        for (int i = 0; i < A.size(); i++)
        {

            if (A[i] == 1)
            {
                v.push_back(i);
            }
        }

        v.push_back(A.size());

        int res = 0;
        if (S == 0)
        {
            for (int i = 1; i < v.size(); i++)
            {
                int dif = v[i] - v[i - 1] - 1;
                res += dif * (dif + 1) / 2;
            }

            return res;
        }

        for (int i = 1; i < v.size() - 1; i++)
        {

            int j = i + S - 1;

            if (j < v.size() - 1)
            {
                int ll = v[i] - v[i - 1];
                int rl = v[j + 1] - v[j];
                res += ll * rl;
            }
        }

        return res;
    }
};

Time Complexity: O(n) Space Complexity: O(n)

Solution: (Prefix Sum)

class Solution
{
public:
    int numSubarraysWithSum(vector<int> &A, int S)
    {

        int n = A.size();
        vector<int> ps(n);
        unordered_map<int, int> m;
        ps[0] = A[0];
        for (int i = 1; i < n; i++)
        {
            ps[i] = A[i] + ps[i - 1];
        }

        int count = 0;
        for (int i = 0; i < n; i++)
        {
            if (ps[i] == S)
            {
                count++;
            }

            if (m.find(ps[i] - S) != m.end())
            {
                count += m[ps[i] - S];
            }

            m[ps[i]]++;
        }

        return count;
    }
};

Time Complexity: O(n)