Binary Subarrays With Sum Solutions in C++

/// Source : https://leetcode.com/problems/binary-subarrays-with-sum/
/// Author : liuyubobobo
/// Time   : 2018-10-29

#include <iostream>
#include <vector>

using namespace std;


/// Using all 1's index
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int numSubarraysWithSum(vector<int>& A, int S) {

        if(A.size() == 0)
            return S == 0;

        vector<int> ones = {-1};
        for(int i = 0; i < A.size(); i ++)
            if(A[i] == 1)
                ones.push_back(i);
        ones.push_back(A.size());

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

        for(int i = 1; i + S < ones.size(); i ++){
            int l = ones[i] - ones[i - 1];
            int r = ones[i + S] - ones[i + S - 1];
            res += l * r;
        }
        return res;
    }
};


int main() {

    vector<int> A1 = {1,0,1,0,1};
    cout << Solution().numSubarraysWithSum(A1, 2) << endl;
    // 4

    vector<int> A2 = {0,0,0,0,0};
    cout << Solution().numSubarraysWithSum(A2, 0) << endl;
    // 15

    vector<int> A3 = {0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,0};
    cout << Solution().numSubarraysWithSum(A3, 3) << endl;
    // 48

    return 0;
}

/// Source : https://leetcode.com/problems/binary-subarrays-with-sum/
/// Author : liuyubobobo
/// Time   : 2018-10-29

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;


/// Using PreSum and HashMap
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int numSubarraysWithSum(vector<int>& A, int S) {

        if(A.size() == 0)
            return S == 0;

        vector<int> sum(A.size() + 1, 0);
        for(int i = 0; i < A.size(); i ++)
            sum[i + 1] = A[i] + sum[i];

        unordered_map<int, int> freq; // sum, freq
        freq[0] ++;

        int res = 0;
        for(int i = 0; i < A.size(); i ++){
            res += freq[sum[i + 1] - S];
            freq[sum[i + 1]] ++;
        }
        return res;
    }
};


int main() {

    vector<int> A1 = {1,0,1,0,1};
    cout << Solution().numSubarraysWithSum(A1, 2) << endl;
    // 4

    vector<int> A2 = {0,0,0,0,0};
    cout << Solution().numSubarraysWithSum(A2, 0) << endl;
    // 15

    vector<int> A3 = {0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,0};
    cout << Solution().numSubarraysWithSum(A3, 3) << endl;
    // 48

    return 0;
}

/// Source : https://leetcode.com/problems/binary-subarrays-with-sum/
/// Author : liuyubobobo
/// Time   : 2018-10-27

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;


/// Two Pointers
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int numSubarraysWithSum(vector<int>& A, int S) {

        if(A.size() == 0)
            return S == 0;

        if(S == 0)
            return dealZero(A);

        unordered_map<int, int> nextZero;
        int lastOne = -1;
        for(int i = 0; i < A.size(); i ++)
            if(A[i] == 0 && lastOne >= 0)
                nextZero[lastOne] ++;
            else if(A[i] == 1)
                lastOne = i;

        unordered_map<int, int> prevZero;
        lastOne = -1;
        for(int i = A.size() - 1; i >= 0; i --)
            if(A[i] == 0 && lastOne >= 0)
                prevZero[lastOne] ++;
            else if(A[i] == 1)
                lastOne = i;

        int l = 0, r = -1, sum = 0, res = 0;
        while(l < A.size()){
            if(r + 1 < A.size() && sum < S){
                sum += A[++r];
            }
            else
                sum -= A[l++];

            if(sum == S && A[l] && A[r])
                res += (nextZero[r] + 1) * (prevZero[l] + 1);
        }
        return res;
    }

private:
    int dealZero(const vector<int>& A){
        int res = 0, start = 0;
        for(int i = start + 1; i <= A.size(); i ++)
            if(i == A.size() || A[i] != A[start]){
                if(A[start] == 0){
                    int n = i - start;
                    // cout << "n : " << n << endl;
                    res += n + n * (n - 1) / 2;
                }
                start = i;
                i = start;
            }
        return res;
    }
};


int main() {

    vector<int> A1 = {1,0,1,0,1};
    cout << Solution().numSubarraysWithSum(A1, 2) << endl;
    // 4

    vector<int> A2 = {0,0,0,0,0};
    cout << Solution().numSubarraysWithSum(A2, 0) << endl;
    // 15

    vector<int> A3 = {0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,0};
    cout << Solution().numSubarraysWithSum(A3, 3) << endl;
    // 48

    return 0;
}

/// Source : https://leetcode.com/problems/binary-subarrays-with-sum/
/// Author : liuyubobobo
/// Time   : 2018-10-29

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;


/// Three Pointers
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int numSubarraysWithSum(vector<int>& A, int S) {

        int i_low = 0, i_high = 0;
        int sum_low = 0, sum_high = 0;
        int res = 0;
        for(int j = 0; j < A.size(); j ++){
            sum_low += A[j];
            while(sum_low > S)
                sum_low -= A[i_low ++];

            sum_high += A[j];
            while((sum_high > S || (sum_high == S && A[i_high] == 0)) && i_high < j)
                sum_high -= A[i_high ++];

            if(sum_low == S)
                res += (i_high - i_low + 1);
        }
        return res;
    }
};


int main() {

    vector<int> A1 = {1,0,1,0,1};
    cout << Solution().numSubarraysWithSum(A1, 2) << endl;
    // 4

    vector<int> A2 = {0,0,0,0,0};
    cout << Solution().numSubarraysWithSum(A2, 0) << endl;
    // 15

    vector<int> A3 = {0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,0};
    cout << Solution().numSubarraysWithSum(A3, 3) << endl;
    // 48

    return 0;
}