用窗口查找Sum

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

您应该能够通过认识到当窗口从一个索引滑动到下一个索引时，一个和与下一个和之间的唯一区别是正好加了一个项，正好减了一个项来提高性能。

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

Answer 2

解决这个问题的一个更简单的方法是，您可以将每个求和结果保存在一个名为current的变量中，而不是执行两次循环来获取窗口中的部分和。然后每次你向右移动窗口，一个元素被移出，一个新元素被移进。所以你可以通过添加新的移入元素和减去旧的移出元素来更新窗口和。这样可以节省一些计算。总体时间复杂度为O(N)。代码如下:

   public class WindowSum {
        public static int[] windowSum(int[] arr, int windowSize) {
            int[] sum = new int[arr.length-windowSize+1];
            int current = 0;
            for(int i=0; i<windowSize; i++)
                current += arr[i];
            sum[0] = current;
            for(int i=1; i<arr.length-windowSize+1; i++) {
                sum[i] = current + arr[i+windowSize-1] - arr[i-1];
                current = sum[i];
            }
            return sum;
        }
        public static void main(String[] args) {
            int[] num = {4, 2, 73, 11, -5};
            int[] sum = windowSum(num, 2);
            System.out.println(Arrays.toString(sum));
        }
    }

Answer 3

这看起来像是一个家庭作业问题，所以我只给出一个关于算法的提示，而不是实际的代码:

• 首先计算第一个窗口的答案。保存在0槽位。
• 对于每个下一步，将窗口1向右移动:添加落在窗口中的新整数，并减去旧整数。保存到下一个插槽。
• 重复，直到窗口的末端碰到输入数据的末端。