專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

3月29號晚上的這起事故讓三個年輕的女孩不幸離世，原因是她們駕駛的時候使用智能輔助駕駛，以116km/h的速度行駛，速度倒不是很快。但突然遇到前面修路，需要變到逆向車道，而車輛檢測到路障之后開始減速，同時駕駛員開始接管車輛，然后持續減速并于隔離帶水泥樁發生碰撞，碰撞前的車速約為97km/h，具體過程如下。

3月29日 22:44:24 車輛發出風險提示“請注意前方有障礙”，并開始減速。

3月29日 22:44:25 車輛被接管，進入人駕狀態，方向盤往左轉角22.0625度，制動踏板開度31%。

3月29日 22:44:26 方向盤往右轉角1.0625度，制動踏板開度38%。

3月29日 22:44:26-28之間 車輛與水泥護欄發生碰撞。

智能駕駛雖好但也不能完全依賴它，我開車的時候只有在車輛稍微多的時候才打開智能駕駛，因為車輛比較多的話，速度都不會很快，智能駕駛會根據前車的速度進行調整。但如果車輛比較少的話，我開車的速度是很快的，如果交給智駕，我肯定是不放心的，總有一種脫離約束馬上就會撞上的感覺。

而SU7的這起事故，雷軍深夜發文回應，并表示：無論發生什么，小米都不會回避。很多網友對雷軍的回復表示支持，并表示車輛出現事故應該找保險公司，找交警，而不是找廠家。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第1343題：大小為 K 且平均值大于等于閾值的子數組數目，難度是中等。

給你一個整數數組 arr 和兩個整數 k 和 threshold 。請你返回長度為 k 且平均值大于等于 threshold 的子數組數目。

示例1：

輸入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4 輸出：3 解釋：子數組 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分別為 4，5 和 6 。其他長度為 3 的子數組的平均值都小于 4 （threshold 的值)。

示例2：

輸入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5 輸出：6 解釋：前 6 個長度為 3 的子數組平均值都大于 5 。注意平均值不是整數。

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

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

• 1 <= k <= arr.length

• 0 <= threshold <= 10^4

問題分析

這題說的是給定一個數組，讓計算數組中有多少長度為 k ，且平均值大于等于threshold的子數組，這是一道典型的滑動窗口問題。我們還可以把這題改一下：計算數組中有多少長度為 k ，且總和為 k*threshold 的子數組。

我們固定窗口的大小為 k ，直接累加窗口中的所有元素，如果窗口中所有元素的和大于等于k*threshold，說明當前窗口是滿足條件的，繼續滑動窗口，繼續判斷。

關于滑動窗口，我之前也整理了三個，一個是大小可變窗口，一個是固定窗口，還一個是只增不減窗口，每一個都有一個對應的代碼模板，具體可以看下《算法秘籍》的第八章，而這題是一道長度固定的窗口，我們只需要把代碼模板拿過來稍微修改下即可。

JAVA：

public int numOfSubarrays(int[] arr, int k, int threshold) {     int sum = 0, ans = 0, target = k * threshold;     for (int i = 0; i < arr.length; i++) {         sum += arr[i];// 累加窗口中的值         if (i + 1 >= k) {// 窗口長度             if (sum >= target)                 ans++;// 滿足條件的個數             sum -= arr[i + 1 - k];// 窗口左邊界的值移除窗口。         }     }     return ans; }

C++：

public:     int numOfSubarrays(vector

 &arr, int k, int threshold) {         int sum = 0, ans = 0, target = k * threshold;         for (int i = 0; i < arr.size(); i++) {             sum += arr[i];// 累加窗口中的值             if (i + 1 >= k) {// 窗口長度                 if (sum >= target)                     ans++;// 滿足條件的個數                 sum -= arr[i + 1 - k];// 窗口左邊界的值移除窗口。             }         }         return ans;     }

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。