Số mảng con có Kích thước K và Trung bình Lớn hơn hoặc Bằng với Ngưỡng trong C ++

Giả sử chúng ta có một mảng các số nguyên arr và hai số nguyên k và ngưỡng. Chúng ta phải tìm số mảng con có kích thước k và trung bình lớn hơn hoặc bằng ngưỡng. Vì vậy, nếu đầu vào là:[2,2,2,2,5,5,5,8] và k =3 và ngưỡng =4, thì đầu ra sẽ là 3. Bởi vì các mảng con [2,5,5] , [5,5,5] và [5,5,8] có giá trị trung bình lần lượt là 4, 5 và 6.

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

• sum:=0, div:=k và n:=số phần tử trong mảng

• set sum:=tổng tất cả các phần tử của arr

• ret:=0

• đối với i:=0 và j trong phạm vi k đến n - 1, hãy tăng cả i và j lên 1

  • nếu sum / div> =ngưỡng, sau đó tăng res lên 1

  • giảm tổng của arr [i]

  • tăng tổng bằng arr [j]

• nếu sum / div> =ngưỡng, sau đó tăng ret lên 1

• trả lại ret.

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

Đầu vào

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

Đầu ra

3