Algorithm
Problem Name: 1248. Count Number of Nice Subarrays
Problem Link: https://leetcode.com/problems/count-number-of-nice-subarrays/
Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it.
Return the number of nice sub-arrays.
Example 1:
Input: nums = [1,1,2,1,1], k = 3 Output: 2 Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].
Example 2:
Input: nums = [2,4,6], k = 1 Output: 0 Explanation: There is no odd numbers in the array.
Example 3:
Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2 Output: 16
Constraints:
1 <= nums.length <= 500001 <= nums[i] <= 10^51 <= k <= nums.length
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
class Solution:
def numberOfSubarrays(self, nums: List[int], k: int, cnt: int = 0) -> int:
odds = [-1] + [i for i, num in enumerate(nums) if num % 2] + [len(nums)]
return sum(
(odds[j - k + 1] - odds[j - k]) * (odds[j + 1] - odds[j])
for j in range(k, len(odds) - 1)
)
Input
nums = [1,1,2,1,1], k = 3
Output
2