C++에서 크기가 K이고 평균이 임계값보다 크거나 같은 하위 배열의 수

정수 arr와 두 개의 정수 k 및 임계값의 배열이 있다고 가정합니다. 크기가 k이고 임계값보다 크거나 같은 평균의 하위 배열 수를 찾아야 합니다. 따라서 입력이 [2,2,2,2,5,5,5,8] 및 k =3 및 임계값 =4와 같으면 출력은 3이 됩니다. 하위 배열 [2,5,5] , [5,5,5] 및 [5,5,8]의 평균은 각각 4, 5, 6입니다.

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

• sum :=0, div :=k 및 n :=배열의 요소 수

• set sum :=arr의 모든 요소의 합

• 렛 :=0

• k ~ n – 1 범위의 i :=0 및 j에 대해 i와 j를 모두 1만큼 증가

  • sum / div>=임계값이면 res를 1만큼 증가

  • arr[i]에 의해 합계 감소

  • arr[j]만큼 합계 증가

• sum / div>=임계값이면 ret를 1만큼 증가

• 반환 반환.

예시(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int numOfSubarrays(vector<int>& arr, int k, int threshold) {
      double sum = 0;
      double div = k;
      int n = arr.size();
      for(int i = 0; i < k; i++){
         sum += arr[i];
      }
      int ret = 0;
      for(int i = 0, j = k; j < n; i ++, j++){
         if(sum / div >= threshold ){
            ret++;
         }
         sum -= arr[i];
         sum += arr[j];
      }
      if(sum / div >= threshold ){
         ret++;
      }
      return ret;
   }
};
main(){
   vector<int> v = {2,2,2,2,5,5,5,8};
   Solution ob;
   cout << (ob.numOfSubarrays(v, 3, 4));
}

입력

[2,2,2,2,5,5,5,8]
3
4

출력

3