サイズKの部分配列のうち平均が閾値以上になる個数をC++で求める方法

整数型の配列 arr と、2つの整数 k および threshold が与えられます。このとき、サイズが k で平均が threshold 以上となる部分配列（サブアレイ）の個数を求めるのが目的です。

例として、入力が [2,2,2,2,5,5,5,8]、k = 3、threshold = 4 の場合を考えてみましょう。このとき出力は 3 になります。これは、部分配列 [2,5,5]、[5,5,5]、[5,5,8] の平均がそれぞれ 4、5、6 となり、いずれも閾値 4 以上だからです。

解法のアプローチ（スライディングウィンドウ）

この問題は、スライディングウィンドウ（尺取り法）を使えば効率的に解けます。ウィンドウ内の合計値を管理し、要素を1つずつずらしながら平均を判定していくことで、配列を一度走査するだけで答えが求まります。

具体的な手順は以下の通りです。

• sum := 0、div := k、n := 配列の要素数 とする
• sum に配列 arr の先頭 k 個の要素の合計を代入する
• ret := 0（答えを格納する変数）で初期化する
• i := 0、j を k から n - 1 の範囲で、i と j を同時に1ずつ増やしながら繰り返す
  • sum / div >= threshold であれば ret を1増やす
  • sum から arr[i] を引く（ウィンドウの左端を除外）
  • sum に arr[j] を足す（ウィンドウの右端を追加）
• ループ終了後、最後のウィンドウに対して sum / div >= threshold であれば ret を1増やす
• ret を返す

この方法では、各ウィンドウの合計を毎回再計算する必要がなく、差分のみを更新するため、時間計算量は O(n)、空間計算量は O(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

この実装では、最初にサイズ k のウィンドウの合計を計算し、その後ウィンドウを1つずつ右にずらしながら条件を判定しています。最後のウィンドウはループ内で判定されないため、ループ後に個別にチェックしている点に注意してください。