Блог

Этот вопрос из leetcode . Мой вывод верен, и 123 / 123 тестовых примера пройдены, но заняли слишком много времени. Можете ли вы помочь мне улучшить тот же код, который у меня есть?

Вопрос: Учитывая массив, состоящий из n целых чисел, найдите непрерывный подмассив заданной длины k, который имеет максимальное среднее значение. И вам нужно вывести максимальное среднее значение.

Пример 1:

Ввод: [1,12,-5, -6,50,3], k = 4 Вывод: 12,75 Объяснение: максимальное среднее значение равно (12-5-6 50)/4 = 51/4 = 12.75

 class Solution {
    public double findMaxAverage(int[] nums, int k) {
     
        
        int i = 0;
        int j = 0;
        double max = Integer.MIN_VALUE;
        while(i k <= nums.length){ 
             
         double sum = 0;
            while(i < k   j){ 
             sum  = nums[i]; 
                i  ;
                }    
            max = Math.max(max, sum);
            j  ;
            i = j;
        }
        
        return max/k;
    }
}
  

• Я думаю, может быть, он застрянет в одном из while s.

• Мы можем решить проблему O(N) :

 public class Solution {
    public static final double findMaxAverage(
        final int[] nums,
        final int k
    ) {
        long currSum = 0;

        for (int index = 0; index < k; index  ) {
            currSum  = nums[index];
        }

        long maxSum = currSum;

        for (int index = k; index < nums.length; index  ) {
            currSum  = nums[index] - nums[index - k];
            maxSum = Math.max(maxSum, currSum);
        }

        return (double) maxSum / k;

    }
}