假设我们有一个整数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
让我们看下面的实现以更好地理解-
#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