Leetcode 930. Binary Subarrays With Sum

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

解析：Version 1暴力法，超时。Version 2，统计前i个元素和total出现的次数，S出现的次数等于每一个total - S出现的次数的和。

• Version 1

class Solution:
    def numSubarraysWithSum(self, A, S):
        n = len(A)
        count = 0
        for i in range(n):
            total = A[i]
            if total == S:
                count += 1
            for j in range(i + 1, n):
                total += A[j]
                if total > S:
                    break
                if total == S:
                    count += 1
        return count

• Version 2

class Solution(object):
    def numSubarraysWithSum(self, A, S):
        n = len(A)
        result = 0
        total = 0
        count = collections.Counter({0 : 1})
        for i in range(n):
            total += A[i]
            result += count[total - S]
            count[total] += 1
        return result

Reference

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