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

Question

我有一个算法可以生成包含所有可能值之和的二维数组。例如，对于数组 [1,5,8,4,5]，二维数组 sums[1][3] 应该 return 原始数组 (17) 中索引 1-3 的总和。我相信在大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) 时间内用前缀和数组解决这个问题 space:

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

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

Answer 2

按以下方式计算 prefix 总和：

public static int[] sum(int[] values){
    int[] prefix_sums = new int[values.length];
    prefix_sums[0] = values[0];
    for(int x = 1; x < values.length; x++){
        prefix_sums[x] = prefix_sums[x-1] + values[x];
    }
    return prefix_sums;
}

根据您的查询，您想要找到从索引 x 到索引 y 的总和（基于 0 的索引），这是获取总和的方法：

if(x==0)
    result = prefix_sums[y];
else
    result = prefix_sums[y] - prefix_sums[x-1];

希望对您有所帮助！！！

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

How can I make this Algorithm more efficient?

algorithm

big-o

time-complexity

data-structures