【Leetcode_easy】643. Maximum Average Subarray I

problem

题意：一定长度的子数组的最大平均值。

solution1:计算子数组之后的常用方法是建立累加数组，然后再计算任意一定长度的子数组之和，迭代更新得到最大值。

注意：1)累加数组；2)数值类型；

class Solution {

public:

    double findMaxAverage(vector<int>& nums, int k) {

        vector<int> sum(nums.size(), );

        //vector<int> sum = nums;

        for(int i=; i<nums.size(); ++i)//err.

        {

            if(i==) sum[] = nums[i];

            else sum[i] = sum[i-] + nums[i];//err.

        }

        double mx = sum[k-];

        for(int i=; i<nums.size()-k; ++i)

        {

            mx = max(mx, (double)sum[i+k]-sum[i]);//err.

        }

        /*

        for(int i=k; i<nums.size(); ++i)

        {

            mx = max(mx, (double)sum[i]-sum[i-k]);

        }

        */

        return mx/k;

    }

};

solution2:

子数组的长度k是确定的，所以其实没有必要建立整个累加数组，而是先算出前k个数字的和，然后就像维护一个滑动窗口一样，将窗口向右移动一位，即加上一个右边的数字，减去一个左边的数字，就等同于加上右边数字减去左边数字的差值，然后每次更新结果res即可。

注意：如何求解k个连续数值之和，这里使用accumulate函数。

class Solution {

public:

    double findMaxAverage(vector<int>& nums, int k) {

        double sum = accumulate(nums.begin(), nums.begin()+k, );//

        double res = sum;

        for(int i=k; i<nums.size(); ++i)

        {

            sum += nums[i] - nums[i-k];

            res = max(res, sum);

        }

        return res/k;

    }

};

参考

1. Leetcode_easy_643. Maximum Average Subarray I;

2. Grandyang;

完

巴特西

【Leetcode_easy】643. Maximum Average Subarray I

最新文章

热门文章