leetcode 2090. 半径为 k 的子数组平均值

一、题目描述

给你一个下标从 $0$ 开始的数组 nums，数组中有 $n$个整数，另给你一个整数 $k$ 。
半径为 $k$ 的子数组平均值 是指：nums中一个以下标 $i$ 为 中心 且 半径 为 $k$ 的子数组中所有元素的平均值，即下标在 $i - k$ 和 $i + k$ 范围（含 $i - k$ 和 $i + k$）内所有元素的平均值。如果在下标 $i$ 前或后不足 $k$ 个元素，那么 半径为 $k$ 的子数组平均值 是 $-1$ 。
构建并返回一个长度为 $n$ 的数组 $avgs$ ，其中 $avgs[i]$ 是以下标 i 为中心的子数组的 半径为 $k$ 的子数组平均值 。
输入：nums = [7,4,3,9,1,8,5,2,6], k = 3
输出：[-1,-1,-1,5,4,4,-1,-1,-1]
来源：leetcode 2090. 半径为 k 的子数组平均值

二、解题报告

1、思路分析

滑动窗口：以i为中心，k为半径的窗口，滑动即是减去前边的数，加上后边的数。

2、代码详解

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* getAverages(int* nums, int numsSize, int k, int* returnSize){
    int *ret=(int *)malloc(sizeof(int)*numsSize);
    int l,r;
    long long sum[100005],div=2*k+1;
    
    *returnSize=numsSize;
    for(int i=0;i<numsSize;i++){
        ret[i]=-1;
    }
    for(int i=k;i<numsSize-k;i++){
        if(i==k){
            sum[i]=0;
            for(int j=0;j<div;j++){
                sum[i]+=nums[j];
            }//创建窗口
        }else{
            sum[i]=sum[i-1]-nums[i-k-1]+nums[i+k];
        }//窗口滑动
    }
    for(int i=k;i<numsSize-k;i++){
        ret[i]=sum[i]/div;
    }
    return ret;
}

借鉴：英雄哪里出来

打赏