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 are 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.lengthclass Solution {
public int numberOfSubarrays(int[] nums, int k) {
int n = nums.length, lt = 0, rt = 0, ct = 0, ans = 0;
while (rt < n) {
while (rt < n && ct < k) {
if (nums[rt] % 2 == 1)
ct++;
rt++;
}
if (ct != k)
break;
int ltFlank = 0, rtFlank = 0;
while (lt < n && nums[lt] % 2 == 0) {
ltFlank++;
lt++;
}
while (rt < n && nums[rt] % 2 == 0) {
rtFlank++;
rt++;
}
ans += (ltFlank + 1) * (rtFlank + 1);
lt++;
ct--;
}
return ans;
}
}