C++에서 좋은 부분배열의 개수 세기

정수 num과 정수 k의 배열이 있다고 가정합니다. 하위 배열은 k 개의 홀수가 있는 경우 nice 하위 배열로 알려져 있습니다. 우리는 좋은 하위 배열의 수를 찾아야 합니다. 따라서 배열이 [1,1,2,1,1]이고 k =3이면 하위 배열이 [1,1,2,1]이고 [1,2,1]이므로 출력은 2가 됩니다. ,1]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

ans :=0, n :=nums 배열의 크기
왼쪽 :=0 및 오른쪽 :=0, 개수 :=0
배열을 홀수로 정의하고 숫자에 있는 모든 홀수 값으로 채우기
홀수 배열의 길이가>=k이면
- i가 0이고 범위 k – 1에서 j가 홀수 – 1인 경우 i와 j를 1만큼 증가
  - left :=홀수[i] + i =0이면 1, 그렇지 않으면 홀수[i] – 홀수[i – 1]
  - 오른쪽 :=홀수[j] 크기가 홀수인 경우 – 1 =j, 그렇지 않은 경우 홀수[j + 1] – 홀수[j]
  - ans :=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