Số Lượng Mảng Con Kích Thước K Và Trung Bình Lớn Hơn Hoặc Bằng Ngưỡng Trong C++

Giả sử mảng số nguyên arr và hai số nguyên k, threshold. Tìm số lượng mảng con kích thước k có trung bình lớn hơn hoặc bằng threshold. Ví dụ: [2,2,2,2,5,5,5,8], k=3, threshold=4 → 3. Các mảng con: [2,5,5], [5,5,5], [5,5,8] có trung bình 4, 5, 6.

Để giải quyết, chúng ta làm theo các bước:

• sum = 0, div = k, n = arr.size().

• sum = tổng k phần tử đầu.

• ret = 0.

• Với i=0, j=k; j < n; i++, j++: nếu sum/div >= threshold thì ret++; sum -= arr[i]; sum += arr[j].

• Kiểm tra cửa sổ cuối: nếu sum/div >= threshold thì ret++.

• Trả về ret.

Ví dụ (C++)

Hãy xem 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;
    }
};

int 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