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

題意

給定一個數字陣列，找出長度為 k ，且平均值大於 threshold 的 subarray 個數

限制

• 1 <= arr.length <= $10^5$

• 1 <= arr[i] <= $10^4$

• 1 <= k <= arr.length

• 0 <= threshold <= $10^4$

思考題目

• 當需要檢查的長度固定為 k ，只要維護一個固定長度的window就能遍歷每個 subarray

• threashold * k 最大值為 $10^9$，用 與其計算 sum / k <= threshold，不如計算 threshold x k <= sum來避免較慢的浮點數計算

Coding 流程

• 計算 threshold * k 作為新的 threshold

• 計算 arr[0,,k] 的陣列和，並計算是否大於 threshold

• 由迴圈 i in 0..arr.size() - k ，逐步移動window

  • 將 sum 扣除 arr[i]，表示移除舊window的數字

  • 將 sum 加上 arr[i + k]，表示加入新數字並完成移動window

  • 判斷 sum 是否大於等於 threshold 來增加答案計數

Solution

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        const int n = arr.size();

        threshold *= k;
        int sum = accumulate(arr.begin(), arr.begin() + k, 0);
        int ans = threshold <= sum;

        for (int i = 0; i < n - k; i += 1) {
            sum -= arr[i];
            sum += arr[i + k];
            ans += threshold <= sum;
        }
        return ans;
    }
};