算法面試真題詳解：滑動視窗内數的和

給你一個大小為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