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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int NumberOfSubarrays(int[] nums, int k) {
6 int result = 0, oddCount = 0;
7 var prefixCount = new Dictionary<int, int>();
8 prefixCount[0] = 1;
9
10 foreach (int num in nums) {
11 if (num % 2 != 0) {
12 oddCount++;
13 }
14 if (prefixCount.ContainsKey(oddCount - k)) {
15 result += prefixCount[oddCount - k];
16 }
17 if (!prefixCount.ContainsKey(oddCount)) {
18 prefixCount[oddCount] = 0;
19 }
20 prefixCount[oddCount]++;
21 }
22
23 return result;
24 }
25}This C# solution builds on the concept of tracking odd counts via a dictionary to find the number of nice subarrays efficiently. The use of the Dictionary class allows for quick access and updates.
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)
1public class Solution {
2 public int numberOfSubarrays(int[] nums, int k) {
3 int count = 0;
4 for (int start = 0; start < nums.length; start++) {
5 int oddCount = 0;
6 for (int end = start; end < nums.length; end++) {
7 if (nums[end] % 2 == 1) {
8 oddCount++;
9 }
10 if (oddCount == k) {
11 count++;
12 } else if (oddCount > k) {
13 break;
14 }
15 }
16 }
17 return count;
18 }
19}This Java solution uses two nested loops to explore all possible subarrays and counts the odd numbers within each. If the subarray meets the criteria of a nice subarray, it increments the total count.