# 查找平均數最少的子數組 > 原文： [https://www.geeksforgeeks.org/find-subarray-least-average/](https://www.geeksforgeeks.org/find-subarray-least-average/) 給定大小為 n 且整數為 k 的數組 arr []，使得 k < = n。 **示例**： ``` Input: arr[] = {3, 7, 90, 20, 10, 50, 40}, k = 3 Output: Subarray between indexes 3 and 5 The subarray {20, 10, 50} has the least average among all subarrays of size 3. Input: arr[] = {3, 7, 5, 20, -10, 0, 12}, k = 2 Output: Subarray between [4, 5] has minimum average ``` [](https://practice.geeksforgeeks.org/problem-page.php?pid=169) ## 強烈建議您在繼續解決方案之前，單擊此處進行練習。 **簡單解決方案**是將每個元素視為大小為 k 的子數組的開頭，并計算從該元素開始的子數組的總和。 該解決方案的時間復雜度為 O（nk）。 **有效解決方案**是要在`O(n)`時間和`O(1)`額外空間中解決上述問題。 這個想法是使用大小為 k 的滑動窗口。 跟蹤當前 k 個元素的總和。 要計算當前窗口的總和，請刪除上一個窗口的第一個元素，然后添加當前元素（當前窗口的最后一個元素）。 ``` 1) Initialize res_index = 0 // Beginning of result index 2) Find sum of first k elements. Let this sum be 'curr_sum' 3) Initialize min_sum = sum 4) Iterate from (k+1)'th to n'th element, do following for every element arr[i] a) curr_sum = curr_sum + arr[i] - arr[i-k] b) If curr_sum < min_sum res_index = (i-k+1) 5) Print res_index and res_index+k-1 as beginning and ending indexes of resultant subarray. ``` 下面是上述算法的實現。 ## C++ ```cpp // A Simple C++ program to find minimum average subarray #include <bits/stdc++.h> using namespace std; // Prints beginning and ending indexes of subarray // of size k with minimum average void findMinAvgSubarray(int arr[], int n, int k) { ????// k must be smaller than or equal to n ????if (n < k) ????????return; ????// Initialize? beginning index of result ????int res_index = 0; ????// Compute sum of first subarray of size k ????int curr_sum = 0; ????for (int i = 0; i < k; i++) ????????curr_sum += arr[i]; ????// Initialize minimum sum as current sum ????int min_sum = curr_sum; ????// Traverse from (k+1)'th element to n'th element ????for (int i = k; i < n; i++) { ????????// Add current item and remove first item of ????????// previous subarray ????????curr_sum += arr[i] - arr[i - k]; ????????// Update result if needed ????????if (curr_sum < min_sum) { ????????????min_sum = curr_sum; ????????????res_index = (i - k + 1); ????????} ????} ????cout << "Subarray between [" << res_index << ", " ?????????<< res_index + k - 1 << "] has minimum average"; } // Driver program int main() { ????int arr[] = { 3, 7, 90, 20, 10, 50, 40 }; ????int k = 3; // Subarray size ????int n = sizeof arr / sizeof arr[0]; ????findMinAvgSubarray(arr, n, k); ????return 0; } ```