LeetCode 每日一题

子数组最大平均数 I

image.png

思路

双指针
这是一道简单题,通过维护遍历元素,进行左右指针右移进行计算比较,代码中采用了一丢丢的优化。

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double ans = Double.NEGATIVE_INFINITY;
        double sum = 0;
        int len = nums.length;
        int left = 0,right=0;
        if(len>=k){ //边界条件处理
            while(right<len){
                while(right<k){
                    sum += nums[right++];  //此过程为对长度为k中的元素求和
                }
                ans = Math.max(ans, sum/k);
                if(right>=k && right<len){
                    sum -= nums[left++];  // 一个小技巧就是无需每次对重新遍历k个元素求和,只需减去左指针元素加上右指针元素求和即可
                    sum += nums[right++];
                }
            }
        }
        ans = Math.max(ans, sum/k); // 此环节不可缺少,因为在while内部循环的时候少了当right遍历到最后索引,但是还是少了求平均的过程
        return ans;
    }
}

关于作者

Kirago
扯淡第一名
获得点赞
文章被阅读