<p>Given an array of integers <code>nums</code> and an integer <code>k</code>. A continuous subarray is called <strong>nice</strong> if there are <code>k</code> odd numbers on it.</p>

<p>Return <em>the number of <strong>nice</strong> sub-arrays</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,2,1,1], k = 3
<strong>Output:</strong> 2
<strong>Explanation:</strong> The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,4,6], k = 1
<strong>Output:</strong> 0
<strong>Explanation:</strong> There are no odd numbers in the array.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,2,2,1,2,2,1,2,2,2], k = 2
<strong>Output:</strong> 16
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 50000</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10^5</code></li>
	<li><code>1 &lt;= k &lt;= nums.length</code></li>
</ul>

#include <vector>
#include <iostream>
static const bool Booster = [](){
    std::ios_base::sync_with_stdio(false);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
    return true;
}();
class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        std::vector <int>odd_index;
        for(int i=0;i<nums.size();i++){
            if(nums[i]&1){odd_index.push_back(i);}
        }
        
        if(odd_index.size()<k){return 0;}
        std::vector <int>prev_index {odd_index};
        //prev_index[0] = odd_index[0];
        for(int i=1;i<odd_index.size();i++){
            prev_index[i] = odd_index[i] - odd_index[i-1] -1;
        }

        std::vector <int>next_index {odd_index};
        for(int i=0;i<odd_index.size()-1;i++){
            next_index[i] = odd_index[i+1] - odd_index[i] -1;
        }
        int sum=0;
        next_index.back() = nums.size()-odd_index.back()-1;
        /*for(auto i:odd_index){std::cout<<i;}std::cout<<std::endl;
        for(auto i:prev_index){std::cout<<i;}std::cout<<std::endl;
        for(auto i:next_index){std::cout<<i;}std::cout<<std::endl;*/
        for(int first = 0;first<=odd_index.size()-k;first++){
            int second = first + k-1;
            /*std::cout << "first " << first << " second " << second<< std::endl;
            std::cout << "before " << prev_index[first] << " after " << next_index[second]<< std::endl;
            std::cout << "variants " << (1+prev_index[first])*(1+next_index[second])<<std::endl;*/
            sum+=(1+prev_index[first])*(1+next_index[second]);
        
        
        }
    return sum;
    }
};
65355