Đếm số lượng các tiểu khu Nice trong C ++

Giả sử chúng ta có một mảng các số nguyên num và một số nguyên k. Một mảng con được gọi là mảng con đẹp nếu có k số lẻ trên đó. Chúng ta phải tìm số mảng con đẹp. Vì vậy, nếu mảng là [1,1,2,1,1] và k =3, thì đầu ra sẽ là 2, vì các mảng con là [1,1,2,1] và [1,2,1 , 1]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ans:=0, n:=kích thước của mảng nums
• left:=0 and right:=0 and count:=0
• xác định một mảng lẻ, điền vào mảng này với tất cả các giá trị lẻ có trong nums
• nếu độ dài của mảng lẻ là> =k, thì
  • đối với tôi là 0 và j trong phạm vi k - 1 đến kích thước là lẻ - 1, tăng i và j lên 1
    • trái:=lẻ [i] + 1 nếu i =0, ngược lại là lẻ [i] - lẻ [i - 1]
    • phải:=lẻ [j] nếu kích thước là lẻ - 1 =j, ngược lại là lẻ [j + 1] - lẻ [j]
    • ans:=ans + left * right
• trả lại ans

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

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

Đầu ra

2