Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold ใน C++

ให้ Array arr, Integer k, threshold หาจำนวน **Subarrays ความยาว k** ที่ **Average ≥ Threshold**

ตัวอย่าง

arr = [2,2,2,2,5,5,5,8], k=3, threshold=4

• Subarrays of size 3:
• [2,2,2] Avg=2 < 4
• [2,2,2] Avg=2 < 4
• [2,2,5] Avg=3 < 4
• [2,5,5] Avg=4 ≥ 4 ✓
• [5,5,5] Avg=5 ≥ 4 ✓
• [5,5,8] Avg=6 ≥ 4 ✓

Output: 3

แนวทาง: Sliding Window (Fixed Size K)

1. คำนวณ sum ของ Window แรก k Elements
2. Slide Window: ลบ arr[i] บวก arr[i+k]
3. เช็ค sum / k >= threshold (หรือ sum >= threshold * k หลีกเลี่ยง Floating Point)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        int n = arr.size();
        long long sum = 0; // Use long long to avoid overflow
        for (int i = 0; i < k; i++) sum += arr[i];

        int count = 0;
        long long target = 1LL * threshold * k; // Compare Sum >= Target

        if (sum >= target) count++;

        for (int i = k; i < n; i++) {
            sum += arr[i] - arr[i - k]; // Slide
            if (sum >= target) count++;
        }
        return count;
    }
};

Input / Output

Input:  [2,2,2,2,5,5,5,8] 3 4
Output: 3

ความซับซ้อน (Complexity)

• Time: O(N) — Single Pass
• Space: O(1)

Optimization

ใช้ sum >= threshold * k แทน Division ทำให้ **เร็วกว่าและแม่นยำกว่า** (Integer Arithmetic) ครับ