Dare2Solve
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.
l
(left) and r
(right), both set to the beginning of the array. Use a variable res
to count the number of nice subarrays, and count
to keep track of the number of odd numbers in the current window.r
to the right, expanding the window until the window contains exactly k
odd numbers.k
odd numbers, count how many subarrays end at r
and start at positions between l
and the current l
. Increment res
by the number of valid subarrays.l
to the right to reduce the number of odd numbers in the window. Adjust l
until the window no longer contains k
odd numbers.r
reaches the end of the array.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.
O(n)
, where n
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).O(1)
, since we only use a fixed amount of extra space for pointers and counters.class Solution {
public:
int numberOfSubarrays(vector<int>& 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;
}
};
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
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;
}
}
/**
* @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;
};
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
}
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;
}
}