[C++] 3 ideas, solution, and explanation for beginners
First, the naive solution, we check every possible subarray and increment the count everytime we encounter a nice subarray.\n\nclass Solution {\npublic:\n    in
First, the naive solution, we check every possible subarray and increment the count everytime we encounter a nice subarray.\n```\nclass Solution {\npublic:\n    int numberOfSubarrays(vector<int>& nums, int k) {\n        int n = nums.size();\n        int sum = 0;\n        for(int i = 0; i < n; i++) {\n            int count = 0;\n            for(int j = i; j < n; j++) {\n                if(nums[j] & 1 != 0) {\n                    count++;\n                }\n                \n                if(count == k) sum++;\n                if(count > k) break;\n            }\n        }\n        \n        return sum;\n    }\n};\n```\nVery standard, not much to talk about. The time complexity is `O(n^2)`while the space complexity is `O(1)`. Submitting this will cause an TLE...so it is clear we must do better on time complexity.\n\nHere is an observation, given a minimum length nice subarray with even number surrounding it. The total amount of different subarray we can construct is the "left wing" * "right wing". Take a look at the following example:\n```\n2,2,2,2,1,2,2,1,2,2,2,2       k = 2\n```\nHow many nice subarray can we construct? The answer is `5 * 5 = 25`. While we can count everything out, a better way is to notice the following pattern `1,2,2,1 -> 1,2,2,1,2 -> 1,2,2,1,2,2 -> ...`, for every element in the "left wing" we can pair it up with every other element in the "right wing" and vice versa. Simple math tells us the number of such combination is simply `left wing * right wing`. I will sepereate the two wings to make it clearer `2,2,2,2,1 | 2,2 | 1,2,2,2,2` (notice that we include the odd number in the wing). How we can locate a "minimum length nice subarray"? Easy, we can simple store indexs of all odd numbers and create a sliding window of length `k`. For every such window, we will calculate the length of both wing, either terminate at the start or end of an array, or terminate immediate before another odd number. For example, our minimum length nice subarray is from index 7 to index 9. \n`2,2,1       |       2,2,2,2,1| 2 |1,2,2,2,2        |        1,1`\nIf you don\'t get it, stare at it for a while and I\'m sure it will come to you. Time for the implementation:\n```\nclass Solution {\npublic:\n    int numberOfSubarrays(vector<int>& nums, int k) {\n        int n = nums.size();\n        vector<int> idx;\n        for(int i = 0; i < n; i++) {\n            if(nums[i] & 1 != 0) idx.push_back(i);\n        }\n        \n        int sum = 0;\n        \n        int i = 0;\n        for(int j = k - 1; j < idx.size(); j++) {\n            int left = idx[i] - (i == 0 ? -1 : idx[i - 1]);\n            int right = (j == idx.size() - 1 ? n : idx[j + 1]) - idx[j];\n            \n            sum += left * right;\n            i++;\n        }\n        \n        return sum;\n    }\n};\n```\nTime complexity is `O(n)` while space complexity is also `O(n)`. \n\nSubmit and the code runs fine. I always like looking for other solutions even after finishing a question. I find it a good practice and also interesting that 1 problem can have so many different solutions.\n\nThis question might remind you of https://leetcode.com/problems/subarrays-with-k-different-integers/. This is a great question and I would definitely recommend checking out. When we do our standard sliding window solutions we get stuck because there is no easy way to slide the window through all possible subarrays. However, we can actually find all subarray with ATMOST `k` odd numbers pretty easily with sliding window. You should try and do this on your own. Eitherway, simple math tells us that `exactly(k) = atmost(k) - atmost(k - 1)`. This gives us a relatively simple algorithm:\n```\nclass Solution {\n    \n    int atMost(vector<int>& nums, int k) {\n        int n = nums.size();\n        int i = 0;\n        int sum = 0;\n        \n        for(int j = 0; j < n; j++) {\n            if((nums[j] & 1) != 0) k--;\n            while(k < 0) {\n                if((nums[i] & 1) != 0) k++;\n                i++;\n            }\n            \n            sum += j - i + 1;\n        }\n        \n        return sum;\n    }\n    \npublic:\n    int numberOfSubarrays(vector<int>& nums, int k) {\n        return atMost(nums, k) - atMost(nums, k - 1);\n    }\n};\n```\nSame time complexity as the solution above, but space complexity is `O(1)`.
[]