给你一个大小为n的整型数组和一个大小为k的滑动窗口，将滑动窗口从头移到尾，输出从开始到结束每一个时刻滑动窗口内的数的和。
在线评测地址：
领扣题库官网
样例 1
输入：array = [1,2,7,8,5], k = 3
输出：[10,17,20]
解析：
1 + 2 + 7 = 10
2 + 7 + 8 = 17
7 + 8 + 5 = 20
算法：前缀和，滑动窗口
前缀和就是一个数列的前n项和，前缀和的计算非常简单，我们只需要额外开一个数组来记录它就好了。每次有新的元素出现我们令sum[i] = sum[i - 1] + nums[i]，其中sum是我们用来记录前缀和的数组，nums是我们要输入的数列，i代表数列nums中的第i个数。这样的话我们仅仅需要O(N)的复杂度就可以完成计算，在查询宽度为k的区间之间的值的时候，只需要计算sum[i] - sum[i - k] + nums[i-k]即可
可以理解成是一个会滑动的窗口，每次记录下窗口的状态，再找出符合条件的适合的窗口，这题要求长度为k，我们维护一个区间[l,r]，先计算这个区间的和，然后每次l，r都向右移动一个单位，并减去nums[l]，加上nums[r+1]，得到新的区间的和。
复杂度分析
n为数组的大小
时间复杂度O(n)
空间复杂度O(n)
public class Solution {
/**
* @param nums: a list of integers.
* @param k: length of window.
* @return: the sum of the element inside the window at each moving.
*/
public int[] winSum(int[] nums, int k) {
if (k == 0) {
return new int[0];
}
int n = nums.length;
int[] sum = new int[n];
sum[0] = nums[0];
// 计算前缀和
for (int i = 1;i < n; i++) {
sum[i] = sum[i - 1] + nums[i];
}
k--;
int[] res = new int[n - k];
for (int i = k;i < n; i++) {
res[i - k]= sum[i] - sum[i - k] + nums[i-k];
}
return res;
}
}//滑动窗口public class Solution {
/**
* @param nums: a list of integers.
* @param k: length of window.
* @return: the sum of the element inside the window at each moving.
*/
public int[] winSum(int[] nums, int k) {
if (k == 0) {
return new int[0];
}
int n = nums.length;
int l = 0,r = k - 1,sum = 0;
//计算初始窗口的和
for (int i = 0; i < k; i++) {
sum += nums[i];
}
int[] res = new int[n - k + 1];
int index = 0;
res[index++] = sum;
while (r < n - 1) {
sum -= nums[l];
l++;r++;//窗口右移
sum += nums[r];
res[index++] = sum;
}
return res;
}
}
更多题解参考：
九章官网solution