[C++] ✅ 💯 |Three Approaches | Sliding Window along with Advanced Approach | Prefix Sum | Time: O(n)
Method 1 : Sliding Window Approach\n# Intuition\n Describe your first thoughts on how to solve this problem. \n\nTo solve the problem of counting the number of 
# Method 1 : Sliding Window Approach\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nTo solve the problem of counting the number of nice subarrays (subarrays with exactly k odd numbers), we can use a sliding window approach. This technique helps in efficiently counting subarrays by expanding and contracting the window based on the number of odd numbers within the window. However, instead of directly counting subarrays with exactly k odd numbers, we can count subarrays with at most k odd numbers and subtract the count of subarrays with at most k-1 odd numbers.\n\n# Approach\n## Also I have written comments in the second code for better understanding of each step. You can refer to it.\n<!-- Describe your approach to solving the problem. -->\n1.\t**Helper Function solve(nums, k)**:\n\t-\tThis function returns the count of subarrays with at most k odd numbers.\n\t-\tInitialize two pointers (left and right), a counter for odd numbers (cntOdd), and a counter for subarrays (subarrays).\n\t-\tIterate through the array using the right pointer, and for each element, increment the count of odd numbers if the current element is odd.\n\t-\tIf the count of odd numbers exceeds k, increment the left pointer to reduce the count of odd numbers within the window.\n\t-\tFor each position of the right pointer, add the number of valid subarrays ending at right to subarrays.\n\t\n2.\t**Main Function numberOfSubarrays(nums, k)**:\n\t-\tCall solve(nums, k) to get the count of subarrays with at most k odd numbers.\n\t-\tCall solve(nums, k-1) to get the count of subarrays with at most k-1 odd numbers.\n\t-\tThe difference between these two results gives the count of subarrays with exactly k odd numbers.\n\n# Complexity\n- Time complexity: $$O(n)$$ where `n` is the size of the nums array. Here each element, at max can be traversed twice, i.e., 2*n times. It is the order of n.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n---\n> #### **Code without Comments :-**\n# Code\n```\nclass Solution {\npublic:\n    int solve(vector<int>& nums, int k) {\n        int n = nums.size(), left = 0, right = 0, cntOdd = 0, subarrays = 0;\n        while(right < n) {\n            cntOdd += nums[right] & 1 ;\n            while (cntOdd > k) cntOdd -= nums[left++] & 1;\n            subarrays += right - left + 1;\n            right++;\n        }\n        return subarrays;\n    }\n    int numberOfSubarrays(vector<int>& nums, int k) {\n        return solve(nums,k) - solve(nums,k-1);\n    }\n};\n```\n> #### **Code with comments :-**\n```\nclass Solution {\npublic:\n    // This helper function counts the number of subarrays with at most `k` odd numbers\n    int solve(vector<int>& nums, int k) {\n        int n = nums.size();  // Size of the input array\n        int left = 0;  // Left pointer for the sliding window\n        int right = 0;  // Right pointer for the sliding window\n        int cntOdd = 0;  // Counter for the number of odd numbers in the current window\n        int subarrays = 0;  // Counter for the number of valid subarrays\n\n        // Iterate over the array with the right pointer\n        while (right < n) {\n            // If the current element is odd, increment the odd number counter\n            cntOdd += (nums[right] & 1);\n            \n            // If the count of odd numbers exceeds `k`, adjust the left pointer\n            // to reduce the number of odd numbers in the current window\n            while (cntOdd > k) {\n                cntOdd -= (nums[left++] & 1);\n            }\n            \n            // The number of valid subarrays ending at the current right pointer is\n            // the size of the current window (right - left + 1)\n            subarrays += right - left + 1;\n            \n            // Move the right pointer to the next element\n            right++;\n        }\n        \n        // Return the total count of valid subarrays with at most `k` odd numbers\n        return subarrays;\n    }\n\n    // This function returns the number of subarrays with exactly `k` odd numbers\n    int numberOfSubarrays(vector<int>& nums, int k) {\n        // The number of subarrays with exactly `k` odd numbers is the difference\n        // between the number of subarrays with at most `k` odd numbers and the\n        // number of subarrays with at most `k-1` odd numbers\n        return solve(nums, k) - solve(nums, k-1);\n    }\n};\n```\n\n## Advanced Sliding Window Approach:\n\n- ### **One Pass Sliding Window Approach**:\n\n    > #### **Code without comments**:\n    ```\n    class Solution {\n    public:\n        int numberOfSubarrays(vector<int>& nums, int k) {\n            int n = nums.size(), i = 0, j = 0, prevSubarrayCount = 0, oddNumberCount = 0, totalNiceSubarrays = 0;\n            while(j < n) {\n                if(nums[j++] & 1) oddNumberCount++, prevSubarrayCount = 0;\n                while(oddNumberCount == k)  {\n                    prevSubarrayCount++; \n                    if(nums[i++] & 1) oddNumberCount--;\n                }\n                totalNiceSubarrays += prevSubarrayCount;\n            }\n            return totalNiceSubarrays;\n        }\n    };\n    ```\n    > #### **Code with comments**:\n    ```\n    class Solution {\n    public:\n        int numberOfSubarrays(vector<int>& nums, int k) {\n            // Initialize the size of the array\n            int n = nums.size();\n            // Initialize the pointers for the sliding window\n            int i = 0, j = 0;\n            // This variable keeps track of the count of subarrays ending at the current position\n            // that contain exactly k odd numbers\n            int prevSubarrayCount = 0;\n            // This variable keeps track of the number of odd numbers in the current window\n            int oddNumberCount = 0;\n            // This variable will accumulate the total number of nice subarrays\n            int totalNiceSubarrays = 0;\n            \n            // Traverse the array with the right pointer j\n            while (j < n) {\n                // If the current number is odd, increment the oddNumberCount\n                if (nums[j] & 1) {\n                    oddNumberCount++;\n                    // Reset the count of valid subarrays ending at the current position\n                    prevSubarrayCount = 0;\n                }\n                \n                // While the window contains exactly k odd numbers\n                while (oddNumberCount == k) {\n                    // Increment the count of valid subarrays ending at the current position\n                    prevSubarrayCount++;\n                    // If the number at the left pointer is odd, decrement the oddNumberCount\n                    if (nums[i] & 1) {\n                        oddNumberCount--;\n                    }\n                    // Move the left pointer to shrink the window\n                    i++;\n                }\n                \n                // Add the count of valid subarrays ending at j to the total count\n                totalNiceSubarrays += prevSubarrayCount;\n                // Move the right pointer to expand the window\n                j++;\n            }\n            \n            // Return the total number of nice subarrays after processing the entire array\n            return totalNiceSubarrays;\n        }\n    };\n    ```\n\n---\n# Method 2 : Prefix Sum Approach\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo solve the problem of counting the number of \u201Cnice\u201D subarrays (continuous subarrays containing exactly k odd numbers), we can utilize a combination of prefix sums and hash maps. The main idea revolves around keeping track of the number of odd numbers encountered so far while traversing the array and leveraging this information to count subarrays with exactly k odd numbers.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\t**Prefix Sum with Hash Map**:\n    -\tWe will traverse the array while maintaining a count of the odd numbers encountered so far `oddCount`.\n\t-\tWe\u2019ll use a hash map `freq` to store the frequency of each oddCount.\n\t-\tFor each element in the array, we check if there is a prefix subarray (ending before the current element) that has `oddCount - k` odd numbers. If such a prefix exists, it means there are some subarrays ending at the current element that have exactly `k` odd numbers.\n\t-\tBy summing the frequencies of these prefix subarrays, we can get the count of \u201Cnice\u201D subarrays.\n2.\t**Initialization**:\n\t-\tInitialize a frequency array `freq` to count the occurrences of oddCount. We start with `freq[0] = 1` to handle the case when the first `k` odd numbers are found from the beginning of the array.\n\t-\tTraverse the array, update `oddCount` for each element, and update the result by checking the frequency map.\n\n# Complexity\n- Time complexity: $$O(n)$$ where `n` is the size of nums array.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(50001)$$ = $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(1)$$ -->\n--- \n\n> #### **Code without comments :-**\n# Code\n```\nclass Solution {\npublic:\n    int numberOfSubarrays(vector<int>& nums, int k) {\n        int freq[50001] = {0};\n        freq[0] = 1; \n        int n = nums.size(), oddCount = 0, subarrays = 0;\n        for(int i = 0; i < n; i++) {\n            oddCount += nums[i] & 1;\n            if(oddCount - k >= 0) subarrays += freq[oddCount - k];\n            freq[oddCount]++;\n        }\n        return subarrays;\n    }\n};\n```\n> #### **Code with comments :-**\n```\nclass Solution {\npublic:\n    int numberOfSubarrays(vector<int>& nums, int k) {\n        // Initialize frequency array to count occurrences of oddCount\n        int freq[50001] = {0};\n        freq[0] = 1; \n        \n        int n = nums.size();  // Size of the input array\n        int oddCount = 0;  // Count of odd numbers encountered so far\n        int subarrays = 0;  // Count of nice subarrays\n        \n        for(int i = 0; i < n; i++) {\n            // Update oddCount if current number is odd\n            oddCount += nums[i] & 1;\n            \n            // If there exists a prefix with oddCount - k, add its frequency to subarrays\n            if(oddCount - k >= 0) subarrays += freq[oddCount - k];\n            \n            // Update frequency array for the current oddCount\n            freq[oddCount]++;\n        }\n        \n        return subarrays;  // Return the total count of nice subarrays\n    }\n};\n```\n\n![upvote.jpeg](https://assets.leetcode.com/users/images/ce196c66-2e6f-4dec-8e30-c25c2f1f7fd3_1706881698.9688694.jpeg)\n[Instagram](https://www.instagram.com/iamsidharthaa__/)\n[LinkedIn](https://www.linkedin.com/in/sidharth-jain-36b542133)\n**If you find this solution helpful, consider giving it an upvote! Your support is appreciated. Keep coding, stay healthy, and may your programming endeavors be both rewarding and enjoyable!**
['Array', 'Hash Table', 'Math', 'Sliding Window', 'C++']