时间复杂性改进

Question

我一直在尝试Codility.com的编码挑战，这是我尝试的问题之一:

给出一个由 N 个整数组成的非空零索引数组 A。一对整数 （P， Q），使得 0 ≤ P

例如，数组A如下：

A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8

包含以下示例切片:

切片 （1， 2），其平均值为 （2 2） / 2 = 2;切片 （3， 4），其平均值为 （5 1） / 2 = 3;切片 （1， 4），其平均值为 （2 2 5 1） / 4 = 2.5。目标是找到平均值最小的切片的起始位置。

写一个函数：

class Solution { public int Solution(int[]A)；}

如果给定一个由N个整数组成的非空零索引数组a，则以最小平均值返回切片的起始位置。如果有多个切片具有最小平均值，则应返回此类切片的最小起始位置。

例如，给定数组A，使得:

A[0] = 4
A[1] = 2
A[2] = 2
A[3] = 5
A[4] = 1
A[5] = 5
A[6] = 8

该函数应返回 1，如上所述。

我已经提交了我的答案，得到了60%。我的解决方案是正确的，并且我通过了所有的测试案例。我之所以得到60%是因为时间复杂度。我的解决方案运行大型测试用例的时间太长。

这是我在Java中的解决方案：

class Solution {
    public int solution(int[] A) {
        int size = A.length;

        if (size == 2) {
            return 0;
        }

        int sizeLessOne = size - 1;
        int start       = 0;
        double min      = 0;
        boolean isFirst = true;

        for (int i = 0; i < sizeLessOne; i++) {
            int val1  = A[i];
            for (int j = i + 1; j < size; j++) {
                int val2   = A[j];
                double avg = ((double) val1 + val2) / (j - i + 1);
                if (isFirst || avg < min) {
                    min   = avg;
                    start = i;
                    if (isFirst) {
                        isFirst = false;
                    }
                }
                val1 += val2;
            }
        }

        return start;
    }
}

public class SolutionRunner {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] A    = {4,2,2,5,1,5,8};
        System.out.println(s.solution(A));
    }
}

根据我的代码，由于嵌套的for循环，我最差的时间复杂度是O(N^2).O(N)上的预期最坏情况。我不确定如何实现这一点。

先谢谢你。

Answer 1

您可以在O（n）中执行此操作，因为始终存在大小为2或3的最佳子数组。

假设您有一个大小为n的最优子数组