Q:

Find Sum with Window

I was trying to solve this problem:
There is a list and a window. The window says the number of elements to be added in the list, for example:
[4, 2, 73, 11, -5] and window size 2 should return [6, 75, 84, 6].
So I wrote the code as follows:
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);
        }
    }
}

This does not an efficient solution as time complexity is high. Any help would be appreciated. 

A:

You should be able to better performance by recognizing that as the window slides from one index to the next, the only difference between one sum and the next sum is that exactly one item is added and exactly one item is subtracted.
You don't need to re-compute the sum in a j for loop in each iteration of the i for loop.  Compute the initial sum of the first window numbers first, which will take care of i being 0.  Then in each iteration of the i loop, starting at 1, add in to the sum the value at index window + i and subtract out the value at index i.  This will improve the performance, especially for high values of window.

