Easy C++ Solution || T.C = O(N) || Sliding Window
Intuition\r\nTo solve the problem of counting the number of subarrays with exactly k odd numbers, we can use a sliding window approach. This method allows us to
# Intuition\r\nTo solve the problem of counting the number of subarrays with exactly `k` odd numbers, we can use a sliding window approach. This method allows us to efficiently manage the window of elements in the array and count the number of valid subarrays without needing to recompute for each possible subarray.\r\n\r\n# Approach\r\n1. **Initialize Variables**:\r\n   - `ansCnt` to store the final count of subarrays.\r\n   - `cnt` to store the count of valid subarrays ending at the current position.\r\n   - Two pointers `i` and `j` to maintain the sliding window.\r\n\r\n2. **Sliding Window Expansion**:\r\n   - Iterate over the array using the `j` pointer.\r\n   - If the current element is odd, decrement `k` and reset `cnt` to 0.\r\n   \r\n3. **Sliding Window Contraction**:\r\n   - When `k` becomes 0, start contracting the window from the left (`i` pointer).\r\n   - For each element removed from the window, increment `cnt`.\r\n   - If the removed element is odd, increment `k` to continue expanding the window.\r\n\r\n4. **Counting Valid Subarrays**:\r\n   - Add `cnt` to `ansCnt` after each expansion step to count all valid subarrays ending at position `j`.\r\n\r\n5. **Return Result**:\r\n   - Return `ansCnt` as the final result.\r\n\r\n# Complexity\r\n- **Time Complexity**: $$O(n)$$, where `n` is the length of the array. Each element is processed at most twice (once by `j` and once by `i`).\r\n- **Space Complexity**: $$O(1)$$, as no extra space proportional to the input size is used.\r\n\r\n# Code\r\n```cpp\r\nclass Solution {\r\npublic:\r\n    int numberOfSubarrays(vector<int>& nums, int k) {\r\n        int ansCnt = 0; // Final count of subarrays\r\n        int cnt = 0;    // Count of valid subarrays ending at current position\r\n        int i = 0, j = 0; // Two pointers for the sliding window\r\n\r\n        while (j < nums.size()) {\r\n            if (nums[j] % 2 != 0) { // If the current element is odd\r\n                k--; // Decrement k as we have encountered an odd number\r\n                cnt = 0; // Reset the count of valid subarrays ending at this position\r\n            }\r\n            \r\n            while (k == 0) { // While we have exactly k odd numbers in the window\r\n                if (nums[i] % 2 != 0) { // If the leftmost element of the window is odd\r\n                    k++; // Increment k as we will remove this odd number\r\n                }\r\n                cnt++; // Increment count of valid subarrays ending at current position\r\n                i++; // Move the left pointer of the window to the right\r\n            }\r\n            \r\n            ansCnt += cnt; // Add the count of valid subarrays to the final answer\r\n            j++; // Move the right pointer of the window to the right\r\n        }\r\n\r\n        return ansCnt; // Return the final count of subarrays with exactly k odd numbers\r\n    }\r\n};\r\n```\r\n
['Sliding Window', 'C++']