Array String Hash Map Sliding Window
Intermediate Level

Implement the countNiceSubarrays method that counts subarrays that contain exactly k odd numbers.

The input contains an integer array nums, its length size, and an integer k. A nice subarray is a continuous subarray that contains exactly k odd numbers.

Your task is to count how many nice subarrays exist in the given array.

For example, in [1,1,2,1,1] with k = 3, there are 2 such subarrays.

Example 1
Input:
nums (int[]) = [1,1,2,1,1]
size (int) = 5
k (int) = 3
Return:
(int) 2
Example 2
Input:
nums (int[]) = [2,4,6]
size (int) = 3
k (int) = 1
Return:
(int) 0
Example 3
Input:
nums (int[]) = [2,2,2,1,2,2,1,2,2,2]
size (int) = 10
k (int) = 2
Return:
(int) 16

Track how many odd numbers have been seen so far using a prefix count.

For each position, calculate the current number of odd values seen. To form a subarray with exactly k odd numbers, we need an earlier prefix with odd count equal to currentOddCount - k.

Store how many times each prefix odd count has occurred. Add that stored count to the answer for every position.

Pseudocode:

function countNiceSubarrays(nums, size, k):
    prefixFrequency = empty map
    prefixFrequency[0] = 1
    oddCount = 0
    answer = 0
    for i from 0 to size - 1:
        if nums[i] is odd:
            oddCount++
        needed = oddCount - k
        if needed exists in prefixFrequency:
            answer = answer + prefixFrequency[needed]
        prefixFrequency[oddCount]++
    return answer
Run your code to see the result.