1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

題目連結: 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

題意

給定一個數字陣列 arr，找出長度為 k，且平均值大於或等於 threshold 的子陣列數量。

限制

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^4
• 1 <= k <= arr.length
• 0 <= threshold <= 10^4

思考題目

1. 由於 k 是固定的，我們可以使用固定長度的滑動窗口（Sliding Window）來遍歷所有可能的子陣列。
2. 直接計算 sum / k >= threshold 可能涉及浮點數計算，影響效能，改寫為 sum >= threshold * k 來避免浮點數比較，提升運算速度。
3. 閾值變換技巧：
   • 由於 threshold * k 最大可能值為 10^9，屬於 int 可表示範圍，因此可以安全地使用整數運算來比較。
4. 使用滑動窗口：
   • 計算初始長度 k 的子陣列總和 sum。
   • 透過 O(1) 操作，不斷滑動窗口，將 sum 減去舊元素並加上新元素，來獲取新子陣列的總和。
   • 若 sum 滿足條件，則計數 +1。

解題流程

1. 計算 threshold * k 作為新的比較基準 targetSum，避免浮點數運算。
2. 初始化 arr[0..k] 的總和 sum，並判斷是否符合條件。
3. 使用滑動窗口遍歷 arr[1..n-k]：
   • 移除 arr[i]（舊的窗口左側數字）。
   • 新增 arr[i + k]（新的窗口右側數字）。
   • 若 sum >= targetSum，則計數器 ans +1。
4. 最後回傳 ans。

解法

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        const int n = arr.size();
        int targetSum = threshold * k; // 避免修改 threshold 參數
        int sum = accumulate(arr.begin(), arr.begin() + k, 0);
        int ans = sum >= targetSum;

        for (int i = 0; i < n - k; i++) {
            sum = sum - arr[i] + arr[i + k]; // 移動滑動窗口
            ans += sum >= targetSum;
        }
        return ans;
    }
};

時間與空間複雜度分析

時間複雜度：O(N)

• 初始化 arr[0..k] 總和需要 O(k)。
• 滑動窗口遍歷：
  • 每次迴圈只涉及兩個數值的加減運算（移除 arr[i]，加入 arr[i+k]），總共執行 (N-K) 次，屬於 O(N-K) ≈ O(N)。
• 總計：O(k) + O(N-K) = O(N)，由於 k <= N，所以最終時間複雜度是 O(N)。

空間複雜度：O(1)

• 只使用常數額外變數 (sum、targetSum、ans)，因此額外空間需求為 O(1)。