Detailed Explanation | One Pass, O(1) Space - C++, Python, Java
Approach\n Describe your approach to solving the problem. \nOur goal is to count the number of sub arrays that have exactly k odd numbers. Let\'s take a look at
# Approach\n<!-- Describe your approach to solving the problem. -->\nOur goal is to count the number of sub arrays that have exactly `k` odd numbers. Let\'s take a look at Example 3 where `k = 2` (but I added an extra 1 to the end):\n\n`nums = [2,2,2,1,2,2,1,2,2,2,1]`\n\nOur first nice subarray starts at index 7 since we would have found a sub array with exactly two odd numbers. Furthermore, every subarray starting from index 0 to index 3 and ending at index 7 is also considered nice. Couynting this would be easy as we would just need to decrease our window from the left and count how many times we still have our two odd numbers.\n\nHowever, if you notice, all the sub arrays starting from index 0 (the initial start of our left pointer) up to the 1 at the end of the array, are also considered good subarrays, since we would still have a total of two odd numbers, so we also need to count these. Ending at index 7 we have 4 nice subarrays, and for every even number after index 7, we have the possibility of 4 new nice sub arrays. Therefore, if we want to calculate the amount of nice subarrays, we can repeatedly add the size of the window starting from `l` to the beginning of the first odd number for the current window (which we start to count when we reach a window that has `k` odd numbers).\n\nEverytime we find an odd number, we reset count, because we only count subarrays with exactly `k` odd numbers and since we only increment count when k reaches 0, we get to include all the even numbers that would count as nice subarrays, after we find `k` odd numbers. When we reach to the final 1 at index 10, we decrease our window and count the elements between index 4 and index 6 and add it to our result. With this method, we can effectively count the subarrays that are between the new window containing `k` odd numbers.\n# Complexity\n- Time complexity: $$O(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\n```C++ []\nclass Solution {\npublic:\n    int numberOfSubarrays(vector<int>& nums, int k) {\n        int res = 0, count = 0;\n        for (int l = 0, r = 0; r < nums.size(); r++){\n            if (nums[r] % 2){\n                k--;\n                count = 0;\n            }\n            while (k == 0){\n                count++;\n                k += (nums[l++] % 2);\n            }\n            res += count;\n        }\n        return res;\n    }\n};\n```\n```python []\nclass Solution:\n    def numberOfSubarrays(self, nums: List[int], k: int) -> int:\n        res = count = l = 0\n        for r in range(len(nums)):\n            if nums[r] % 2:\n                k -= 1\n                count = 0\n            while not k:\n                k += (nums[l] % 2)\n                count += 1\n                l += 1\n            res += count\n        return res\n```\n```Java []\nclass Solution {\n    public int numberOfSubarrays(int[] nums, int k) {\n        int res = 0, count = 0;\n        for (int l = 0, r = 0; r < nums.length; r++){\n            if (nums[r] % 2 == 1){\n                k--;\n                count = 0;\n            }\n            while (k == 0){\n                count++;\n                k += (nums[l++] % 2);\n            }\n            res += count;\n        }\n        return res;\n    }\n}\n```\n
['Array', 'Math', 'C', 'Sliding Window', 'C++', 'Java', 'Python3']