leetcode-161周赛-5248-统计【优美子数组】

题目描述：

自己的提交：超时：

class Solution:

    def numberOfSubarrays(self, nums, k: int) -> int:

        dp = [0]* (len(nums)+1)

        res = 0

        for i in range(len(nums)):

            if nums[i] % 2 == 0:

                dp[i+1] = dp[i]

            else:

                dp[i+1] = dp[i] + 1

            if dp[i+1] == k:

                res += 1

        for i in range(len(nums)):

            for j in range(len(nums)+1):

                if nums[i] % 2 == 1:

                    dp[j] -= 1

                if dp[j] == k:

                    res += 1

        return res

参考后提交：O(N)

class Solution:

    def numberOfSubarrays(self, nums, k: int) -> int:

        dp = [0]* (len(nums)+1)

        res = 0

        for i in range(len(nums)):

            if nums[i] % 2 == 0:

                dp[i+1] = dp[i]

            else:

                dp[i+1] = dp[i] + 1

        from collections import Counter

        dic = Counter(dp)

        for i in dp:

            if i >= k:

                res += dic[i-k]

        return res
                

优化：

import collections

class Solution:

    def numberOfSubarrays(self, nums, k: int) -> int:

        mp = collections.Counter()

        mp[0] = 1

        g = 0

        ans = 0

        for num in nums:

            if num % 2 == 1:

                g += 1

            ans += mp[g - k]

            mp[g] += 1

        return ans