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.
1def number_of_subarrays(nums, k):
2 count = 0
3 prefix_count = {0: 1}
4 odd_count = 0
5 result = 0
6
7 for num in nums:
8 if num % 2 == 1:
9 odd_count += 1
10
11 if odd_count - k in prefix_count:
12 result += prefix_count[odd_count - k]
13
14 if odd_count in prefix_count:
15 prefix_count[odd_count] += 1
16 else:
17 prefix_count[odd_count] = 1
18
19 return resultThis solution uses a hash map (dictionary) to count the frequency of certain odd counts (prefix counts). As we iterate over nums, we update the current count of odd numbers. If the current count minus k has been seen before, it means there is a subarray ending at the current position with exactly k odd numbers.
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)
1def number_of_subarrays(nums, k):
2 count = 0
3 for start in range(len(nums)):
4 odd_count = 0
5 for end in range(start, len(nums)):
6 if nums[end] % 2 == 1:
7 odd_count += 1
8 if odd_count == k:
9 count += 1
10 elif odd_count > k:
11 break
12 return countThis Python solution iterates over all possible subarrays starting from each index. For each subarray, it counts the number of odd numbers and checks if this matches k. If matched, the count of nice subarrays is incremented.