algorithm - 我怎样才能使这个算法更有效率？

Question

我有一个算法可以生成一个二维数组，其中包含所有可能值的总和。例如，对于数组 [1,5,8,4,5]，二维数组 sums[1][3] 应该返回索引 1- 的和3 在原始数组 (17) 中。我相信就大 O 而言，效率是 O(N²)。有什么办法可以让这个算法更有效率吗？

public static int[][] sum(int[] values){
    int[][] sums = new int[values.length][values.length];
    for(int x = 0; x < values.length; x++){
        int total = 0;
        for(int y = x; y < values.length; y++) {
            total += values[y];
            sums[x][y] = total;
        }
    }
    return sums;
}

Answer 1

您可以使用前缀和数组在 O(n) 时间和空间内解决此问题:

array    = [1, 5, 8, 4, 5]
prefixes = [1, 6,14,18,23]

sums(1,3) = prefixes[3] - prefixes[0] = 18 - 1 = 17