如果我们计算k
元素的平均值from 0 to k
,我们可以知道平均值from 1 to k
或关于from 0 to k + 1
?两个平均值1 to k
都0 to k + 1
等于或大于第一元素的平均值k
。为什么?从子集from 0 to k
到子集from 1 to k
,意味着删除最少的元素,因此可能不会降低总平均值。从子集from 0 to k
到子集from 0 to k + 1
,意味着添加一个不小于其他元素的元素,因此它可能不会降低总平均值。
我们是否知道给定数组中的哪个数字必须是结果的一部分?是的,这是最后一个小于或等于目标的。为什么?当它相等时,我们就完成了当它不相等时,我们需要同时拥有更大和更低的元素。
然后,我们通过从右侧添加元素并从左侧减少来保持平均值。
public static int[] findMean(int[] input, int target) {
int firstGreater = 0;
int n = input.length;
while(firstGreater < n && input[firstGreater] <= target) firstGreater++; // use binary search instead!
if(firstGreater == 0 || firstGreater == n) return new int[]{-1,-1};
int left = firstGreater - 1, right = firstGreater;
long sum = input[left];
while ((right < n &&(right - left) * target > sum) || (left > 0 && (right - left) * target < sum)) {
if((right - left) * target > sum) sum += input[right++];
else sum += input[--left];
}
if((right - left) * target != sum) {
left = right = -1;
}
return new int[]{left, right - 1};
}