Сначала вы найдете кумулятивные суммы всех индексов. Скажи, что это массив, cumsum[1..n]
Теперь начните с двух указателей, один из которых указывает на первый узел, а второй - на последний. Вычислите среднее значение этого диапазона как (cumsum[last]-cumsum[first])/(last-first+1). Если это больше, чем целевое среднее значение (скажем, k), то переместите указатель назад внутрь, так как это всегда будет уменьшать среднее значение (поскольку оно сортируется). Аналогично, если avg < k, передвиньте передний указатель вперед. Таким образом, вы либо получите диапазон со средним значением k, если он существует, либо поймете, что такого значения k не существует, если передние и задние указатели пересекаются. Поскольку мы перемещаем хотя бы один из указателей на каждом шаге, это O (n).