题目如下:

解题思路:创建一个val数组,val[i]表示从0~i区间内奇数的个数。如果要求i~j区间内奇数的个数,似乎只有val[j] - val[i]即可。但是还要再考虑一点,就是nums[i]的奇偶性。如果nums[i]是奇数,那么区间的奇数数量就是 val[j] - val[i] + 1;否则则为val[j] - val[i]。最后从头开始遍历val,对于每个val[i]来说,只要知道val[i] + k 或者val[i] + k - 1在val整个数组中出现的个数,即可求得nums以第i个元素为首的并且奇数个数为k的子数组的数量。

代码如下:

class Solution(object):
    def numberOfSubarrays(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        count = 0
        val = [0] * len(nums)
        dic = {}
        for i in range(len(nums)):
            if nums[i] % 2 == 1:count += 1
            val[i] = count
            dic[count] = dic.setdefault(count,0) + 1
        #print val

        res = 0

        for i in range(len(nums)):
            if nums[i]%2 == 0:
                key = val[i] + k
            else:
                key = val[i] + k -1
            if key in dic:
                res += dic[key]
        return res
01-06 22:23