Binary Subarrays With Sum Problem


Description

LeetCode Problem 930.

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:

1
2
3
4
5
6
7
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:

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

Constraints:

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


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    int numSubarraysWithSum(vector<int>& A, int S) {
        int left, right, sum, count;
        int last_left, next_left, right_start;
        
        count = 0;
        sum = 0;
        left = 0;
        right_start = 0;
        
        if (S == 0) {
            while ((A[right_start] == 1) && (right_start < A.size()))
                right_start ++;
        }
        
        last_left = right_start;
        next_left = right_start;
        
        for (right = right_start; right < A.size(); right++) {
            sum += A[right];
            if (sum == S) {
                break;
            }
        }
        if (sum < S)
            return 0;
        
        for (; right < A.size(); right++) {
            if (A[right] == 1) {
                last_left = next_left;
            }
            for (left = last_left; left < A.size(); left ++) {
                if (A[left] == 1) {
                    next_left = left + 1;
                    break;
                }
            }
            for (left = last_left; left <= right; left ++) {
                count ++;
                if (A[left] == 1) {
                    break;
                }
            }
            
        }
        
        return count;
    }
};




Related Posts

Fruit Into Baskets Problem

LeetCode 904. You are visiting a farm that has a...

Binary Subarrays With Sum Problem

LeetCode 930. Given a binary array nums and an integer...

Maximum Average Subarray I Problem

LeetCode 643. You are given an integer array nums consisting...

Sliding Window Maximum Problem

LeetCode 239. You are given an array of integersnums, there...

Contains Duplicate III Problem

LeetCode 220. Given an integer array nums and two integers...