給定整數陣列
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
TIP
核心思路：固定大小為 k 的滑動視窗，維護視窗內的總和，判斷平均值是否 >= threshold。
- 平均值 >= threshold 等價於總和 >= threshold * k，避免浮點運算
- 典型的固定大小滑動視窗：每次右移加入新元素、移除最左元素
Approaches
1. Brute Force - Sum Each Subarray — O(n * k) / O(1)
- Idea: 對每個起始位置，計算大小為 k 的子陣列總和
- Time:
O(n * k)- 每個子陣列計算和需 O(k) - Space:
O(1)
Brute Force Code
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 — O(n) / O(1)
- Idea: 維護大小為 k 的視窗總和，每次移動時加入右邊新元素、減去左邊舊元素
- Time:
O(n)- 一次遍歷 - Space:
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
}
}WARNING
用 threshold * k 比較總和，而非計算平均值，可以避免浮點數精度問題。
🔑 Takeaways
- Pattern: 固定大小滑動視窗
- Key trick: 將平均值比較轉換為總和比較（
sum >= threshold * k），是避免浮點運算的常用技巧