專欄：50多種數(shù)據(jù)結構徹底征服
專欄：50多種經典圖論算法全部掌握
3月29號晚上的這起事故讓三個年輕的女孩不幸離世，原因是她們駕駛的時候使用智能輔助駕駛，以116km/h的速度行駛，速度倒不是很快。但突然遇到前面修路，需要變到逆向車道，而車輛檢測到路障之后開始減速，同時駕駛員開始接管車輛，然后持續(xù)減速并于隔離帶水泥樁發(fā)生碰撞，碰撞前的車速約為97km/h，具體過程如下。
3月29日 22:44:24 車輛發(fā)出風險提示“請注意前方有障礙”，并開始減速。
3月29日 22:44:25 車輛被接管，進入人駕狀態(tài)，方向盤往左轉角22.0625度，制動踏板開度31%。
3月29日 22:44:26 方向盤往右轉角1.0625度，制動踏板開度38%。
3月29日 22:44:26-28之間 車輛與水泥護欄發(fā)生碰撞。
智能駕駛雖好但也不能完全依賴它，我開車的時候只有在車輛稍微多的時候才打開智能駕駛，因為車輛比較多的話，速度都不會很快，智能駕駛會根據(jù)前車的速度進行調整。但如果車輛比較少的話，我開車的速度是很快的，如果交給智駕，我肯定是不放心的，總有一種脫離約束馬上就會撞上的感覺。
而SU7的這起事故，雷軍深夜發(fā)文回應，并表示：無論發(fā)生什么，小米都不會回避。很多網友對雷軍的回復表示支持，并表示車輛出現(xiàn)事故應該找保險公司，找交警，而不是找廠家。
--------------下面是今天的算法題--------------
來看下今天的算法題，這題是LeetCode的第1343題：大小為 K 且平均值大于等于閾值的子數(shù)組數(shù)目，難度是中等。
給你一個整數(shù)數(shù)組 arr 和兩個整數(shù) k 和 threshold 。請你返回長度為 k 且平均值大于等于 threshold 的子數(shù)組數(shù)目。
示例1：
輸入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4 輸出：3 解釋：子數(shù)組 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分別為 4，5 和 6 。其他長度為 3 的子數(shù)組的平均值都小于 4 （threshold 的值)。
示例2：
輸入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5 輸出：6 解釋：前 6 個長度為 3 的子數(shù)組平均值都大于 5 。注意平均值不是整數(shù)。
1 <= arr.length <= 10^5
1 <= arr[i] <= 10^4
1 <= k <= arr.length
0 <= threshold <= 10^4
問題分析
這題說的是給定一個數(shù)組，讓計算數(shù)組中有多少長度為 k ，且平均值大于等于threshold的子數(shù)組，這是一道典型的滑動窗口問題。我們還可以把這題改一下：計算數(shù)組中有多少長度為 k ，且總和為 k*threshold 的子數(shù)組。
我們固定窗口的大小為 k ，直接累加窗口中的所有元素，如果窗口中所有元素的和大于等于k*threshold，說明當前窗口是滿足條件的，繼續(xù)滑動窗口，繼續(xù)判斷。
關于滑動窗口，我之前也整理了三個，一個是大小可變窗口，一個是固定窗口，還一個是只增不減窗口，每一個都有一個對應的代碼模板，具體可以看下《算法秘籍》的第八章，而這題是一道長度固定的窗口，我們只需要把代碼模板拿過來稍微修改下即可。
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++;// 滿足條件的個數(shù) 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++;// 滿足條件的個數(shù) sum -= arr[i + 1 - k];// 窗口左邊界的值移除窗口。 } } return ans; }
筆者簡介
博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。
熱門跟貼