🎨Now live: Try our Free AI Image Generation Feature

Intuition
To solve the problem of finding the number of "nice" subarrays (subarrays with exactly k
odd numbers), we can use a two-pointer (or sliding window) approach. The idea is to maintain a window of elements that contains exactly k
odd numbers and calculate how many such subarrays can be formed by shifting the window along the array.
Approach
- Initialize Variables: Start with two pointers,
l
(left) andr
(right), both set to the beginning of the array. Use a variableres
to count the number of nice subarrays, andcount
to keep track of the number of odd numbers in the current window. - Expand the Window: Move the right pointer
r
to the right, expanding the window until the window contains exactlyk
odd numbers. - Count Subarrays: Once the window contains exactly
k
odd numbers, count how many subarrays end atr
and start at positions betweenl
and the currentl
. Incrementres
by the number of valid subarrays. - Shrink the Window: Move the left pointer
l
to the right to reduce the number of odd numbers in the window. Adjustl
until the window no longer containsk
odd numbers. - Repeat: Repeat steps 2-4 until the right pointer
r
reaches the end of the array. - Return Result: Return the total count of nice subarrays stored in
res
.
The approach ensures that we efficiently count the number of subarrays by leveraging the sliding window technique, which avoids the need for nested loops and thus improves performance.
Complexity
- Time Complexity:
O(n)
, wheren
is the length of the input array. Each element is processed at most twice (once by the right pointer and once by the left pointer). - Space Complexity:
O(1)
, since we only use a fixed amount of extra space for pointers and counters.
Code
C++
class Solution {
public:
int numberOfSubarrays(vector& nums, int k) {
int n = nums.size();
int l = 0, r = 0, res = 0;
while (r < n) {
while (r < n && k > 0) if (nums[r++] % 2 != 0) --k;
int i = l;
int j = r;
while (l < r && nums[l] % 2 == 0) ++l;
while (r < n && nums[r] % 2 == 0) ++r;
if (k == 0) res += (l - i + 1) * (r - j + 1);
++l, ++k;
}
return res;
}
};
Python
class Solution:
def numberOfSubarrays(self, nums: List[int], k: int) -> int:
n = len(nums)
l = 0
r = 0
res = 0
while r < n:
while r < n and k > 0:
if nums[r] % 2 != 0:
k -= 1
r += 1
i = l
j = r
while l < r and nums[l] % 2 == 0:
l += 1
while r < n and nums[r] % 2 == 0:
r += 1
if k == 0:
res += (l - i + 1) * (r - j + 1)
l += 1
k += 1
return res
Java
class Solution {
public int numberOfSubarrays(int[] nums, int k) {
int n = nums.length;
int l = 0, r = 0, res = 0;
while (r < n) {
while (r < n && k > 0) if (nums[r++] % 2 != 0) k--;
int i = l;
int j = r;
while (l < r && nums[l] % 2 == 0) l++;
while (r < n && nums[r] % 2 == 0) r++;
if (k == 0) res += (l - i + 1) * (r - j + 1);
l++;
k++;
}
return res;
}
}
JavaScript
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var numberOfSubarrays = function (nums, k) {
var n = nums.length;
var l = 0;
var r = 0;
var res = 0;
while (r < n) {
while (r < n && k) if (nums[r++] & 1) --k;
i = l;
j = r;
while (l < r && !(nums[l] & 1)) ++l;
while (r < n && !(nums[r] & 1)) ++r;
if (!k) res += (l - i + 1) * (r - j + 1);
++l, ++k;
}
return res;
};
Go
func numberOfSubarrays(nums []int, k int) int {
n := len(nums)
l := 0
r := 0
res := 0
for r < n {
for r < n && k > 0 {
if nums[r] % 2 != 0 {
k--
}
r++
}
i := l
j := r
for l < r && nums[l] % 2 == 0 {
l++
}
for r < n && nums[r] % 2 == 0 {
r++
}
if k == 0 {
res += (l - i + 1) * (r - j + 1)
}
l++
k++
}
return res
}
C#
public class Solution {
public int NumberOfSubarrays(int[] nums, int k) {
int n = nums.Length;
int l = 0, r = 0, res = 0;
while (r < n) {
while (r < n && k > 0) if (nums[r++] % 2 != 0) k--;
int i = l;
int j = r;
while (l < r && nums[l] % 2 == 0) l++;
while (r < n && nums[r] % 2 == 0) r++;
if (k == 0) res += (l - i + 1) * (r - j + 1);
l++;
k++;
}
return res;
}
}