用窗口求和

Question

我试图解决这个问题：有一个列表和一个窗口。该窗口显示要添加到列表中的元素数，例如：

[4, 2, 73, 11, -5]和窗口大小2应该返回[6, 75, 84, 6]。

所以我写了如下代码：

public static void main(String args[]){
    LinkedList<Integer> l=new LinkedList<Integer>();
    l.add(5);
    l.add(8);
    l.add(9);
    l.add(3);
    l.add(4);
    l.add(1);
    int window=2;
    int[] sum=new int[l.size()-window+1];

    for(int i=0;i<=l.size()-window; i++){
        for(int j=0;j<window; j++){
            sum[i]=sum[i]+l.get(i+j);
        }
    }
}

这不是一个有效的解决方案，因为时间复杂度很高。任何帮助，将不胜感激。

Answer 1

通过认识到当窗口从一个索引滑动到下一个索引时，您应该能够获得更好的性能，一个总和和下一个总和之间的唯一区别是恰好添加了一项，而恰好减去了一项。

您不需要在j for循环的每次迭代中重新计算循环中的总和i for。首先计算第一个window数字的初始总和，这将处理ibe 0。然后在循环的每次迭代中i，从 开始1，将 index 处的值添加到总和中window + i并减去 index 处的值i。这将提高性能，特别是对于window.