1.題目描述
給你一個(gè)由 n 個(gè)元素組成的整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k 。
請(qǐng)你找出平均數(shù)最大且 長(zhǎng)度為 k 的連續(xù)子數(shù)組，并輸出該最大平均數(shù)。
任何誤差小于 10-5 的答案都將被視為正確答案。
示例 1：
輸入：nums = [1,12,-5,-6,50,3], k = 4
輸出：12.75
解釋：最大平均數(shù) (12-5-6+50)/4 = 51/4 = 12.75
示例 2：輸入：nums = [5], k = 1
輸出：5.00000
2.題目鏈接
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/maximum-average-subarray-i文章來源：http://www.zghlxwxcb.cn/news/detail-703357.html
3.思路講解
筆者最開始解這道題的時(shí)候使用的是暴力解法，結(jié)果最后超過了時(shí)間限度，然后又對(duì)算法進(jìn)行了優(yōu)化，要找出平均數(shù)最大的長(zhǎng)度為 k 的連續(xù)子數(shù)組，那么只需找出總和最大的長(zhǎng)度為 k 的連續(xù)子數(shù)組，首先計(jì)算前k個(gè)數(shù)的和作為初始值，也作為最大值，然后從第k個(gè)數(shù)開始向后移動(dòng)，每次移動(dòng)子數(shù)組和的變化是加上當(dāng)前元素的值，減去當(dāng)前元素的k個(gè)元素之前的值，每次移動(dòng)子數(shù)組就是進(jìn)去一個(gè)數(shù)出去一個(gè)數(shù)。每次移動(dòng)都比較一下當(dāng)前總和與最大值的大小，若大于最大值，則最大值就等于當(dāng)前總和，最后即可找出具有最大總和的長(zhǎng)度為 k 的連續(xù)子數(shù)組，然后除以k，就得到平均數(shù)。文章來源地址http://www.zghlxwxcb.cn/news/detail-703357.html
4.模板代碼
class Solution { public double findMaxAverage(int[] nums, int k) { double ave; int sum=0; //首先計(jì)算前k個(gè)數(shù)的總和作為初始值 for(int i=0;i<k;i++){ sum+=nums[i]; } int max=sum;//也作為最大值 for(int i=k;i<nums.length;i++){ sum=sum+nums[i]-nums[i-k];//每次移動(dòng)總和就等于加上當(dāng)前元素，減去當(dāng)前元素的k個(gè)數(shù)之前的元素 if(sum>max){//與最大值比較，若比最大值大，則最大值等于sum max=sum; } } ave=1.0*max/k; return ave; } }
到了這里，關(guān)于【leetcode17-----子數(shù)組最大平均數(shù)】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
