1248.md

Count Number of Nice Subarrays

Description

link

---

Solution

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

---

Code

O(n) O(n)

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        def Most(k):
            res = 0
            l = 0
            for r in range(len(nums)):
                k -= nums[r] % 2
                while k < 0:
                    k += nums[l] % 2
                    l += 1
                res += r - l + 1
            return res
        return Most(k) - Most(k - 1)