[Sliding Window, Easy] Maximum Average Subarray I

https://leetcode.com/problems/maximum-average-subarray-i/description/?envType=study-plan-v2&envId=leetcode-75

O(N^2) 시간복잡도로 풀면 타임리밋에 걸린다.

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        
        double answer = Integer.MIN_VALUE;

        for (int i=0; i<=nums.length - k; i++) {
            double sum = 0;
            for (int j=i; j<i+k; j++) {
                sum += nums[j];
            }
            double result = sum / k;
            answer = Math.max(answer, result);
        }

        return answer;
    }
}

아래처럼 미리 합을 구해놓고, 윈도우를 옮겨가면서 계산해야 한다 O(N)

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        
        double tempSum = 0;
        for (int i=0; i<k; i++) {
            tempSum += nums[i];
        }

        double max = tempSum;
        for (int i=k; i<nums.length; i++) {
            tempSum += nums[i] - nums[i - k];
            max = Math.max(max, tempSum);
        }    

        return max / k;
    }
}