给出一个由 N 个整数组成的非空零索引数组 A。一对整数 (P, Q)，使得 0 ≤ P < Q < N, is called a slice of array A (notice that the slice contains at least two elements). The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice. To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1).
编写一个函数：
int 解(int A[], int N);
给定一个由 N 个整数组成的非空零索引数组 A，返回具有最小平均值的切片的起始位置。 如果有多个具有最小平均值的切片，则应返回该切片的最小起始位置。
假设：
N是[2..100,000]范围内的整数； 数组 A 的每个元素都是 [−10,000..10,000] 范围内的整数。 复杂性：
预计最坏情况时间复杂度为O(N)； 预期最坏情况的空间复杂度为 O(N)，超出输入存储（不计算输入参数所需的存储）。
你可以只发布顺序为 N 的解决方案吗？
如果
Apos = 0
min_avg = A[0] + A[1]
for (i=2; i<N; i++)
m = A[i-1] + A[i]
if (m < min_avg)
min_avg = m
pos = i-1
return pos
这只是取两个数字的切片的平均值，因为较大切片的平均值不能小于较小切片的最小值。
如果A有负数，可以先将所有值向上调整：
offset = min(A)
for (i=0; i<N; i++)
A[i] -= offset
结合之前的算法：
offset = min(A) * 2 (because we're adding two numbers below)
pos = 0
min_avg = A[0] + A[1] - offset
for (i=2; i<N; i++)
m = A[i-1] + A[i] - offset
if (m < min_avg)
min_avg = m
pos = i-1
return pos
首先，我们应该知道一个数学模式： 当列表的长度大于3时，可以将其分为长度为2和3的若干子分片。例如列表的长度为5，则可以由2和3组成；如果长度为4，则可以由2和2组成。
这样，如果我们有一个长度为 N 的列表：[a, b, c, d, ...]，并且 N > 3，我们将列表中元素的总和设置为 Sum，并且平均值为 Avg = Sum/N。
我们要证明，在这个列表中，至少有一个长度为2或3的子切片的平均值小于或等于Avg。
我们使用反证法，假设所有子切片的平均值都大于 Avg。
将列表分为几个连续的子片，每个子片的长度为 2 或 3，其中最后一个子片的长度可以为 2 或 3：
[a1,a2], [a3，a4]， ......, [aN-2, aN-1, aN] 或者 [a1，a2]， [a3，a4]， ......, [aN-1, aN]
根据我们的假设，每个子切片的平均值都大于Avg；
(a1 + a2)/2 > 平均值； (a3 + a4)/2 > 平均值； ......
将所有不等式相加，我们得到：
(a1 + a2)/2 + (a3 + a4)/2 + ... + (aN-1 + aN)/2 > 平均值 * (N/2)
不等式左边等于 Sum/2 或大于 Sum/2（如果最后一个子切片的长度为 3）；
Sum/2 > Avg * (N/2) => Sum > Avg * N => Sum > (Sum/N) * N => Sum > Sum，这是一个矛盾。
我们得到了矛盾，所以我们的假设不成立。
结论是，如果有一个长度大于3的列表，那么它一定有一个长度为2或3的子切片，其平均值小于或等于整个列表的平均值。
这样我们只需求所有长度为2或3的子切片的最小平均值即可；
这是一个Python版本示例
def solution(A):
n = len(A)
if n == 2:
return 0
min_avg = float('inf')
min_start = 0
for i in range(n - 1):
avg = (A[i] + A[i + 1]) / 2
if avg < min_avg:
min_avg = avg
min_start = i
for i in range(n - 2):
avg = (A[i] + A[i + 1] + A[i + 2]) / 3
if avg < min_avg:
min_avg = avg
min_start = i
return min_start
我认为你是对的，我能做的最好的就是 O(N2) 解决方案（这是在 Python 中）：
from random import randint
N = 1000
A = [randint(-10000, 10000) for _ in xrange(N)]
def solution(A, N):
min_avg = 10001
for p in xrange(N):
s = A[p]
for q in xrange(1,N-p):
s += A[p+q]
a = s / (q+1.)
if a < min_avg:
min_avg = a
pos = (p, q+1)
return pos
print solution(A, N)
但是，较大切片的平均值倾向于原始范围的平均值（中间）。 在这种情况下，平均值为零，介于 -10000 和 10000 之间。大多数情况下，最小平均值是两个值的切片，但有时它可以是三个值的切片，很少可以是更多值。 所以我认为我之前的答案适用于大多数（> 90％）的情况。 这实际上取决于数据值。
#include <assert.h>
struct Slice { unsigned P, Q; };
struct Slice MinSlice( int A[], unsigned N ) {
assert( N>=2 );
// find min slice of length 2
unsigned P = 0;
double min_sum = A[P] + A[P+1];
for (unsigned i = 1; i < N-1; ++i)
if ( min_sum > A[i] +A[i+1] ) {
P = i;
min_sum = A[P] + A[P+1];
}
unsigned Q = P+1;
double min_avg = min_sum / 2;
//extend the min slice if the avg can be reduced.
//(in the direction that most reduces the avg)
for (;;) {
if ( P > 0 && ( Q >= N-1 || A[P-1] <= A[Q+1] ) ) {
//reducing P might give the best reduction in avg
double new_sum = A[P-1] + min_sum;
double new_avg = new_sum / (Q - P + 2);
if ( min_avg < new_avg )
break;
min_sum = new_sum;
min_avg = new_avg;
--P;
} else if ( Q < N-1 && ( P <= 0 || A[P-1] >= A[Q+1] ) ) {
//increasing Q might give the best reduction in avg
double new_sum = min_sum + A[Q+1];
double new_avg = new_sum / (Q - P + 2);
if ( min_avg < new_avg )
break;
min_sum = new_sum;
min_avg = new_avg;
++Q;
} else
break;
}
struct Slice slice = { .P = P, .Q= Q };
return slice;
}