算法面试真题详解:滑动窗口内数的和-阿里云开发者社区

开发者社区> 算法编程> 正文

算法面试真题详解:滑动窗口内数的和

简介: 算法面试真题详解:滑动窗口内数的和

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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接