Найти подмассив в целочисленном массиве с наименьшим средним в одном цикле

Question

Учитывая целочисленный массив и размер подмассива, найдите первый подмассив со средним значением в одном цикле. Выведите первый индекс подмассива и среднего. Проблема в том, что я не могу использовать переменную длину подстроки c без использования какого-либо дополнительного цикла. Мой код -

public void FindFirstSub(int a[], int b, int c)
{
    int average=0,sum=0,leastav=0;
    for(int i=0;i<a.length-c;i++)
    {
        sum = 0;
        sum = a[i]+a[i+1]+a[i+2]; // Here is problem.
        System.out.print(a[i]+" "+a[i+1]+" "+a[i+2]+"\n");
        average = sum/c;
        if(leastav==0)
            leastav=average;
        else if(leastav>average)
            leastav=average;
    }
    System.out.println("Least average is "+leastav);
}

Answer 1

Вы не можете использовать один цикл только для наименьшего среднего, но сложность, которую вы можете поддерживать до O (n).

        static void FindFirstSub(int arr[],int n, int k) 
            { 
              if (n < k) 
                 return; 

            int res_index = 0; 

            int curr_sum = 0; 
            for (int i = 0; i < k; i++) 
                curr_sum += arr[i]; 

            // Initialize minimum sum as current sum 
            int min_sum = curr_sum; 

            for (int i = k; i < n; i++)  
            { 
                // Add current item and remove first 
                // item of previous subarray 
                curr_sum += arr[i] - arr[i - k]; 

                // Update result if needed 
                if (curr_sum < min_sum) { 
                    min_sum = curr_sum; 
                    res_index = (i - k + 1); 
                } 
            } 

            System.out.println("Subarray btw [" + 
                                res_index + ", " + (res_index + k - 1) + 
                                "] has minimum average"); 
        } 

        // Driver method to test the above function 
        public static void main(String[] args) 
        {   
            int arr[] = { 3, 7, 90, 20, 10, 50, 40 }; 
            int k = 3; // Subarray size 
           FindFirstSub(arr.length, k); 
        } 

Answer 2

Вам нужно установить сумму в 0 вне вашего цикла for и оставить промежуточную сумму для суммы. На каждой итерации вычитайте первый элемент предыдущего подмассива, добавляя новый последний элемент нового подмассива. Вы не должны начинать вычитание, пока не достигнете своего второго подмассива или проверки средних значений, пока 'i' не станет последним индексом первого подмассива.