930.和相同的二元子数组

caution

原题链接：https://leetcode.cn/problems/binary-subarrays-with-sum/

思路

求和为 goal 的子数组的个数，可以先使用前缀和求解每个 [0, l] 区间内的和 $\text{sum}_i$，然后找 sum_i - goal 的个数得到子数组的个数。

代码

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        const int N = 3e4 + 10;
        int m[N], ans = 0, sum = 0;
        memset(m, 0, sizeof(m));

        for (int i = 0; i < nums.size(); i++) {
            m[sum]++;
            sum += nums[i];
            if (sum - goal >= 0) {
                ans += m[sum - goal];
            }
        }
        return ans;
    }
};