找出数组中至少包含两个元素的任何切片的最小平均值

Question

完整的问题是：最小平均两层代码

我不明白为什么我的代码不起作用。

我知道正确答案，但我找不到我的代码的反例：

struct partaverg {
    long double min;
    int slice;
};

long long sumfun(int arr[], int N) {
    int sum = 0;
    for (int i = 0; i < N; ++i)
        sum += arr[i];
    return sum;
}

int solution(int A[], int N) {
    long long sum;
    long double new_average;

    int left = 0;
    int right = N - 1;
    long double numofnum;
    long double leftaverg, rightaverg;
    sum = sumfun(A, N);
    struct partaverg result;
    new_average = result.min = sum / (long double)N;
    result.slice = 0;
    while (left + 1 < right) {
        numofnum = right - left;
        leftaverg = (sum - A[left]) / numofnum;
        rightaverg = (sum - A[right]) / numofnum;
        if (leftaverg > rightaverg) {
            sum -= A[right--];
            new_average = rightaverg;
        } else {
            sum -= A[left++];
            new_average = leftaverg;
        }
        if (result.min > new_average) {
            result.min=new_average;
            result.slice=left;
        }
    }
    return result.slice;
}

Answer 1

当当前切片在最左边和最右边的位置保存相同的数字时，你的算法就出现了问题。你应该删除哪个数字？左边还是右边？

您当前的算法始终删除左侧数字，但这可能不正确。考虑：

int arr[4] = {1,9, 10, 1 };

// left average = (1 + 9 + 10) /3
// right average = (9 + 10 + 1) /3

左平均值和右平均值是相同的，因此您的代码删除左数字并继续执行此切片：

{9, 10, 1 };

这是错误的。现在，您无法再获得正确的结果，即：

{1,9};