930. Binary Subarrays With Sum

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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation