题目地址:https://leetcode.com/problems/binary-subarrays-with-sum/description/

题目描述

Inan 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]iseither0or1.;

题目大意

求有多少个子区间的和是S.

解题方法

悲剧啊!周赛第二个题都没做出来。我的想法是双指针,用虫取法的方式去做,但是发现了,当一个区间的前面或者后面都有0的时候,这时候移动前后指针都能达到下一个状态的和也是S。然后我就在上面吊死了。真正的做法如下。

二分查找

这个题考的不是虫取法,题目为什么只给了0和1呢?因为我们每次遇到一个1,整体的和只会增加1,求和的时候不会出现负数,所以如果从左到右求和的过程中是个递增的。

下面的做法有点类似Two sum,最开始先使用一个求和数组保存求和的过程,然后对求和数组tsum做一个遍历,遍历的过程中过程中,使用tsum[i] - S,这个结果remain就是我们要找的前面的部分和。也就是说remain出现的次数就是以i结尾的子数组满足题意的个数。

所以,下面的工作是找到这个remain在tsum中出现了多少次。使用二分查找的lowwer_bound和upper_bound就可以了。需要注意的是有个测试用例全部是0,这个情况下,如果upper_bound就直接找到最右边界了,所以我们得限制一下,upper_bound的索引不能超过当前的i.

时间复杂度是O(NlogN),空间复杂度是O(N)。

class Solution(object):
    def numSubarraysWithSum(self, A, S):
        """
        :type A: List[int]
        :type S: int
        :rtype: int
        """
        N = len(A)
        tsum = [0] * (N + 1)
        for i in range(1, N + 1):
            tsum[i] = tsum[i - 1] + A[i - 1]
        res = 0
        for i in range(1, N + 1):
            remain = tsum[i] - S
            if remain < 0:
                continue
            left = bisect.bisect_left(tsum, remain)
            right = bisect.bisect_right(tsum, remain)
            right = min(i, right)
            res += right - left
        return res

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

字典

在上面的做法中,我们想到了要查找remain出现了多少次,那么我们肯定想起来了使用字典啊!如果用字典的话不能直接先求所有的累计和,然后统计每个和出现了多少次,因为那样的话对全0的输入又蒙了!所以我们需要知道截止到某个位置的时候,当前的和减去S已经出现了多少次。所以这个字典是保存每个和已经出现的次数的!

使用一个字典保存数组某个位置之前的数组和,然后遍历数组求和,这样当我们求到一个位置的和的时候,向前找sum-k是否在数组中,如果在的话,更新结果为之前的结果+1。同时,当前这个sum出现的次数就多了一次。

560. Subarray Sum Equals Kopen in new window几乎一模一样的题目,为什么就是不会做呢?

class Solution(object):
    def numSubarraysWithSum(self, A, S):
        """
        :type A: List[int]
        :type S: int
        :rtype: int
        """
        N = len(A)
        res = 0
        preS = 0
        count = collections.Counter({0 : 1})
        for i in range(1, N + 1):
            preS += A[i - 1]
            res += count[preS - S]
            count[preS] += 1
        return res

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

相似题目

560. Subarray Sum Equals Kopen in new window

参考资料

https://leetcode.com/problems/binary-subarrays-with-sum/discuss/186683/C++JavaPython-Straight-Forward

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发