930.md

Binary Subarrays With Sum

Description

link

---

Solution

• 右边保持滑动，左边保存两个变量l，r分别代表从l，r到右边区间内存在K个以及K-1个不同整数的区间
• 此时答案即为加上r-l即可

---

Code

O(n) O(1)

class Solution:
    def numSubarraysWithSum(self, A: List[int], S: int) -> int:
        def Most(S):
            if S < 0: return 0
            res = l = 0
            for r in range(len(A)):
                S -= A[r]
                while S < 0:
                    S += A[l]
                    l += 1
                res += r - l + 1
            return res
        return Most(S) - Most(S - 1)