计算C ++中Nice子数组的数量

假设我们有一个整数nums和一个整数k的数组。如果子数组上有k个奇数,则称为子数组。我们必须找到漂亮的子数组的数量。因此,如果数组为[1,1,2,1,1],并且k = 3,则输出将为2,因为子数组为[1,1,2,1]和[1,2,1 ,1]

为了解决这个问题,我们将遵循以下步骤-

  • ans:= 0,n:= nums数组的大小

  • 左:= 0和右:= 0,然后计数:= 0

  • 定义一个奇数数组,用以num表示的所有奇数值填充它

  • 如果奇数数组的长度> = k,则

    • 左:=如果i = 0,则为奇数[i] + 1,否则为奇数[i] –奇数[i – 1]

    • 右:=奇数[j]如果奇数的大小– 1 = j,否则奇数[j +1] –奇数[j]

    • ans:= ans +左*右

    • 因为i为0,且j在k – 1到奇数– 1的范围内,所以将i和j加1

    • 返回ans

    例子(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

    输出结果

    2