给你一个大小为 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;     } }  

大佬有話說 (0)