Today I have done leetcode's March LeetCoding Challenge with cpp.

March LeetCoding Challenge 14

Description

Binary Subarrays With Sum

Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum goal.

A subarray is a contiguous part of the array.

Example 1:

Input: nums = [1,0,1,0,1], goal = 2
Output: 4
Explanation: The 4 subarrays are bolded and underlined below:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]

Example 2:

Input: nums = [0,0,0,0,0], goal = 0
Output: 15

Constraints:

• 1 <= nums.length <= 3 * 104
• nums[i] is either 0 or 1.
• 0 <= goal <= nums.length

Solution

class Solution {
public:
  int numSubarraysWithSum(vector<int>& nums, int goal) {
    vector<int> zeros;
    int zero = 0;
    for(auto n : nums) {
      if(n) {
        zeros.push_back(zero);
        zero = 0;
      } else {
        zero += 1;
      }
    }
    zeros.push_back(zero);
    int answer = 0;
    if(goal) {
      for(int i = 0; i + goal < zeros.size(); ++i) {
        answer += (zeros[i] + 1) * (zeros[i + goal] + 1);
      }
    } else {
      for(auto zero : zeros) {
        answer += (1 + zero) * zero / 2;
      }
    }
    return answer;
  }
};