[LeetCode] 930. Binary Subarrays With Sum

[grandyang]

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]
[1,0,1,0]
[0,1,0,1]
[1,0,1]

Note:

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

这道题给了我们一个只由0和1组成的数组A，还有一个整数S，问数组A中有多少个子数组使得其和正好为S。博主最先没看清题意，以为是按二进制数算的，但是看了例子之后才发现，其实只是单纯的求和而已。那么马上就想着应该是要建立累加和数组的，然后遍历所有的子数组之和，但是这个遍历的过程还是平方级的复杂度，这道题的 OJ 卡的比较严格，只放行线性的时间复杂度。所以这种遍历方式是不行的，但仍需要利用累加和的思路，具体的方法是在遍历的过程中使用一个变量 curSum 来记录当前的累加和，同时使用一个 HashMap，用来映射某个累加出现的次数，初始化需要放入 {0,1} 这个映射对儿，后面会讲解原因。在遍历数组的A的时候，对于每个遇到
的数字 num，都加入累加和 curSum 中，然后看若 curSum-S 这个数有映射值的话，那么说明就存在 m[curSum-S] 个符合题意的子数组，应该加入到结果 res 中，假如 curSum 正好等于S，即 curSum-S=0 的时候，此时说明从开头到当前位置正好是符合题目要求的子数组，现在明白刚开始为啥要加入 {0,1} 这个映射对儿了吧，就是为了处理这种情况。然后此时 curSum 的映射值自增1即可。其实这道题的解法思路跟之前那道 Contiguous Array 是一样的，那道题是让找0和1个数相同的子数组，这里让找和为S的子数组，都可以用一个套路来解题，参见代码如下：

解法一：

class Solution {
public:
    int numSubarraysWithSum(vector<int>& A, int S) {
        int res = 0, curSum = 0;
        unordered_map<int, int> m{{0, 1}};
        for (int num : A) {
            curSum += num;
            res += m[curSum - S];
            ++m[curSum];
        }
        return res;
    }
};

我们也可以使用滑动窗口 Sliding Window 来做，也是线性的时间复杂度，其实还是利用到了累计和的思想，不过这个累加和不是从开头到当前位置之和，而是这个滑动窗口内数字之和，这 make sense 吧，因为只要这个滑动窗口内数字之和正好等于S了，即是符合题意的一个子数组。遍历数组A，将当前数字加入 sum 中，然后看假如此时 sum 大于S了，则要进行收缩窗口操作，左边界 left 右移，并且 sum 要减去这个移出窗口的数字，当循环退出后，假如此时 sum 小于S了，说明当前没有子数组之和正好等于S，若 sum 等于S了，则结果 res 自增1。此时还需要考虑一种情况，就是当窗口左边有连续0的时候，因为0并不影响 sum，但是却要算作不同的子数组，所以要统计左起连续0的个数，并且加到结果 res 中即可，参见代码如下：

解法二：

class Solution {
public:
    int numSubarraysWithSum(vector<int>& A, int S) {
        int res = 0, sum = 0, left = 0, n = A.size();
        for (int i = 0; i < n; ++i) {
            sum += A[i];
            while (left < i && sum > S) sum -= A[left++];
            if (sum < S) continue;
            if (sum == S) ++res;
            for (int j = left; j < i && A[j] == 0; ++j) {
                ++res;
            }
        }
        return res;
    }
};

Github 同步地址:

#930

参考资料：

https://leetcode.com/problems/binary-subarrays-with-sum/

https://leetcode.com/problems/binary-subarrays-with-sum/discuss/276976/C%2B%2B

https://leetcode.com/problems/binary-subarrays-with-sum/discuss/186683/C%2B%2BJavaPython-Sliding-Window-O(1)-Space

LeetCode All in One 题目讲解汇总(持续更新中...)