C++ में नाइस सबएरे की संख्या गिनें

मान लीजिए कि हमारे पास पूर्णांक संख्याओं की एक सरणी है और एक पूर्णांक k है। एक सबअरे को अच्छा सबअरे के रूप में जाना जाता है यदि उस पर k विषम संख्याएँ हों। हमें अच्छे उप-सरणियों की संख्या ज्ञात करनी है। तो यदि सरणी [1,1,2,1,1] है, और k =3 है, तो आउटपुट 2 होगा, क्योंकि उप-सरणी [1,1,2,1] और [1,2,1] हैं ,1]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

उत्तर:=0, n:=अंक सरणी का आकार
बाएं:=0 और दाएं:=0, और गिनती:=0
एक सरणी को विषम परिभाषित करें, इसे अंकों में मौजूद सभी विषम मानों से भरें
यदि विषम सरणी की लंबाई>=k है, तो
- के लिए i 0 है और j रेंज k-1 से विषम -1 के आकार में है, i और j को 1 से बढ़ाएं
  - बाएं:=विषम[i] + 1 यदि i =0, अन्यथा विषम[i] - विषम[i - 1]
  - दाएं:=विषम[j] यदि विषम का आकार – 1 =j, अन्यथा विषम[j + 1] – विषम[j]
  - उत्तर:=उत्तर + बाएँ * दाएँ
वापसी उत्तर

उदाहरण(C++)

आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int numberOfSubarrays(vector<int>& nums, int k) {
      int ans = 0;
      int n = nums.size();
      int left = 0;
      int right = 0;
      int cnt = 0;
      vector <int> odd;
      for(int i = 0; i < n; i++){
         if(nums[i] % 2 == 1)odd.push_back(i);
      }
      if(odd.size()>=k){
         for(int i = 0, j = k-1; j < odd.size(); i++, j++){
            int left = i==0?odd[i]+1: odd[i] - odd[i-1];
            int right = j==odd.size()-1 ?n-odd[j] : odd[j+1] - odd[j];
            ans += left * right;
         }
      }
      return ans;
   }
};
main(){
   vector<int> v = {1,1,2,1,1};
   Solution ob;
   cout <<ob.numberOfSubarrays(v, 3);
}

इनपुट

[1,1,2,1,1]
3