643 LeetCode 子数组最大平均数I

题目描述:
643 LeetCode 子数组最大平均数I
思路:
如果每个子数组的和都重新计算一遍的话,会超值超时,因此计算子数组的时候,减去最前面的一个数,然后加上新的数,就是中间的数不变;

代码如下:

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double sum=0;
        double xsum=0;
        for(int i=0;i<k;i++){
            sum+=nums[i];
        }
        xsum=sum;
        for(int i=k;i<nums.size();i++){
            sum=sum+nums[i]-nums[i-k];
            xsum=max(sum,xsum);
        }
        return xsum/k;
    }
};

猜你喜欢