1343. Number of Sub Arrays of Size K and Avg Greater than or Equal to Threshold

Medium
Description

給定整數陣列 arr、整數 k 和整數 threshold，回傳大小為 k 且平均值 >= threshold 的子陣列數量。

Example:

Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4 Output: 3（[2,5,5], [5,5,5], [5,5,8] 平均值分別為 4, 5, 6）

Intuition#

核心思路：固定大小為 k 的滑動視窗，維護視窗內的總和，判斷平均值是否 >= threshold。

  • 平均值 >= threshold 等價於總和 >= threshold * k，避免浮點運算
  • 典型的固定大小滑動視窗：每次右移加入新元素、移除最左元素

Approaches#

1: Brute Force - 計算每個子陣列的和#

  • 概念: 對每個起始位置，計算大小為 k 的子陣列總和
  • 時間複雜度: O(n * k) - 每個子陣列計算和需 O(k)
  • 空間複雜度: O(1)
Brute Force 程式碼
class Solution {
    fun numOfSubarrays(arr: IntArray, k: Int, threshold: Int): Int {
        var count = 0
        for (i in 0..arr.size - k) {
            var sum = 0
            for (j in i until i + k) sum += arr[j]
            if (sum >= threshold.toLong() * k) count++
        }
        return count
    }
}

⭐2: Fixed Sliding Window#

  • 概念: 維護大小為 k 的視窗總和，每次移動時加入右邊新元素、減去左邊舊元素
  • 時間複雜度: O(n) - 一次遍歷
  • 空間複雜度: O(1)
class Solution {
    fun numOfSubarrays(arr: IntArray, k: Int, threshold: Int): Int {
        var windowSum = 0
        var count = 0
        val target = threshold.toLong() * k

        for (i in arr.indices) {
            windowSum += arr[i]
            if (i >= k) {
                windowSum -= arr[i - k]
            }
            if (i >= k - 1 && windowSum >= target) {
                count++
            }
        }
        return count
    }
}

用 threshold * k 比較總和，而非計算平均值，可以避免浮點數精度問題。

🔑 Takeaways#

  • Pattern: 固定大小滑動視窗
  • 關鍵技巧: 將平均值比較轉換為總和比較（sum >= threshold * k），是避免浮點運算的常用技巧