The main idea is to use a sliding window to keep track of the current subarray and count of odd numbers. If the count of odd numbers becomes more than k, move the start pointer to decrease the count. For every suitable subarray, calculate the number of possible subarrays that end at the current end pointer. This way, we can efficiently count the nice subarrays.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n) for the dictionary to store prefix counts.
1import java.util.HashMap;
2
3public class Solution {
4 public int numberOfSubarrays(int[] nums, int k) {
5 int count = 0, oddCount = 0, result = 0;
6 HashMap<Integer, Integer> prefixCount = new HashMap<>();
7 prefixCount.put(0, 1);
8
9 for (int num : nums) {
10 if (num % 2 == 1) {
11 oddCount++;
12 }
13 if (prefixCount.containsKey(oddCount - k)) {
14 result += prefixCount.get(oddCount - k);
15 }
16 prefixCount.put(oddCount, prefixCount.getOrDefault(oddCount, 0) + 1);
17 }
18
19 return result;
20 }
21}Like the Python solution, this Java solution uses a HashMap to count the frequency of odd counts (prefix counts). We iterate over nums, updating the count of odd numbers, and use the HashMap to track previously seen odd counts. If a previously seen odd count matches the current count minus k, it contributes to the number of nice subarrays.
This approach involves checking every possible subarray of nums and counting the odd numbers in each. If a subarray contains exactly k odd numbers, it is counted as nice. While straightforward to implement, this method is not efficient for large arrays as its time complexity is quadratic.
Time Complexity: O(n^2), where n is the length of nums.
Space Complexity: O(1)
1function numberOfSubarrays(nums, k) {
2 let count = 0;
3 for (let start = 0; start < nums.length; start++) {
4 let oddCount = 0;
5 for (let end = start; end < nums.length; end++) {
6 if (nums[end] % 2 !== 0) {
7 oddCount++;
8 }
9 if (oddCount === k) {
10 count++;
11 } else if (oddCount > k) {
12 break;
13 }
14 }
15 }
16 return count;
17}This JavaScript solution evaluates all possible subarrays by counting odd numbers and checking if they form a nice subarray. It's simpler to implement but inefficient for large inputs as every pair of indices is considered.