Count Number of Nice Subarrays

Problem

Given an integer array nums and an integer k, count the contiguous subarrays that contain exactly k odd numbers. Subarrays are identified by their position, so equal-looking subarrays at different positions count separately.

• nums has between 1 and 50,000 positive integers.
• k is between 1 and the length of nums.

Examples

• nums = [3, 5, 8, 7, 9], k = 3 → 2. [3, 5, 8, 7] and [5, 8, 7, 9] each contain three odd numbers; the whole array contains four.
• nums = [4, 8, 10], k = 1 → 0. No odd numbers at all.
• nums = [6, 6, 3, 6, 6, 6, 5, 6, 6], k = 2 → 9. Both odd numbers must be included; there are 3 choices for the left boundary and 3 for the right.

Hints

1. Replace each number by 1 if odd and 0 if even. What is the question now asking about that binary array?
2. Counting subarrays with sum exactly k can be done with prefix sums and a hash map of how often each prefix value has occurred.
3. Alternatively, count windows with at most k odds using a sliding window and subtract the count for at most k - 1.