【leetcode】- Binary Subarrays With Sum（二进制子数组的和问题）

1、题目描述

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]

Note:

   1.A.length <= 30000
   2.0 <= S <= A.length
   3.A[i] is either 0 or 1.

2、问题描述：

• 一个二进制数组，求数组中可以可以组成和为S的子数组有多少个。

3、问题关键：

• 不能用的做法，因为n<= 3000.
• 前缀和。
• 看有多少个j，使s[i] - s[j] = s.
• 枚举i, s[i] - s[j] = s, s[i] - s = s[j] =>f[s[i] - s]。

• 一句话也就是说前面到底有多少个前缀可以使s[i] - s[j] = s.

4、C++代码：

/*
1.前缀和 s[i]  = A[0] + A[1] + ... + A[i]
2.f[i] 表示当前有多少个j， 满足s[j] = i, 表示s[] 里面有多少个数的和为i。
3.枚举i, s[i] - s[j] = s, s[i] - s =  s[j] =>f[s[i] - s] 
*/
class Solution {
public:
    int numSubarraysWithSum(vector<int>& A, int S) {
        int n = A.size();
        vector<int> sum(n + 1, 0), f(n + 1, 0);
        
        for (int i = 0; i < n; i ++) sum[i + 1] = sum[i] + A[i];//前n项和，不用考虑边界问题，将sum[0] = 0;
        
        f[0] = 1;//因为sum[0] = 0,所以肯定有一个符合。
        int res = 0;
        for (int i = 1; i <= n; i ++) {
            if (sum[i] >= S) res += f[sum[i] - S] ;//加上前面总共有多少个和为s[i] - S的。
            f[sum[i]] ++;//f[j]表示的就是将和为sum[i] 的记录到f里面，和为sum[i]可能有多个。
        }
        return res;
    }
};