Binary Subarrays With Sum

930. Binary Subarrays With Sum

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        int l = 0, r = 0, len = nums.size(), g = nums[0], result = 0;
        if (goal) {
            int rl = 0, ll = 0;
            while (g < goal && ++r < len) if (nums[r]) ++g;
            while (r != len) {
                ll = rl = 0;
                while (r + ++rl < len && nums[r + rl] == 0);
                while (l + ll <= r && nums[l + ll++] == 0);
                result += ll * rl;
                r = r + rl;
                l = l + ll;
            }
        } else {
            while (r < len) {
                while (++r < len && nums[r] == 0);
                while (l < r && nums[l]) ++l;
                result += (r - l) * (r - l + 1) / 2;
                l = ++r;
            }
        }
        return result;
    }
};

two poiner 로 goal 개수 만큼 1 시작을 l, 끝을 r 로 한다.
l, r 바깥의 0 경우의 수 만큼이 현재 pointer 로 만들수 있는 sub array 의 수 이므로 이 값을 result 에 더한다.
모든 l, r 을 찾아 동일하게 개수를 구하면 된다.

goal 이 0 일때는, 이어진 0 수에 대한 경우의 수 이므로 0 개수를 구해 등차수열의 합을 구한다.

two pointer 를 오른쪽으로 옮기면, 다음 1의 위치 만큼이 바깥 0의 수이므로 l, r 을 1회 오른쪽으로 옮기면 된다.

Time: O(n)
Space: O(1)