Medium

题目描述

给你一个下标从 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 的子数组平均值 。

x 个元素的 平均值 是 x 个元素相加之和除以 x ，使用截断式 整数除法 ，即需要去掉结果的小数部分。

  • 例如，四个元素 2、3、1 和 5 的平均值是 (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75，截断后得到 2 。

示例 1：

输入：nums = [7,4,3,9,1,8,5,2,6], k = 3
输出：[-1,-1,-1,5,4,4,-1,-1,-1]
解释：
- avg[0]、avg[1] 和 avg[2] 是 -1 ，因为在这些下标前的元素数量都不足 k 个。
- 中心为下标 3 且半径为 3 的子数组的元素总和是：7 + 4 + 3 + 9 + 1 + 8 + 5 = 37 。
  使用截断式整数除法，avg[3] = 37 / 7 = 5 。
- 中心为下标 4 的子数组，avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4 。
- 中心为下标 5 的子数组，avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4 。
- avg[6]、avg[7] 和 avg[8] 是 -1 ，因为在这些下标后的元素数量都不足 k 个。

示例 2：

输入：nums = [100000], k = 0
输出：[100000]
解释：
- 中心为下标 0 且半径为 0 的子数组的元素总和是：100000 。
  avg[0] = 100000 / 1 = 100000 。

示例 3：

输入：nums = [8], k = 100000
输出：[-1]
解释：
- avg[0] 是 -1 ，因为在下标 0 前后的元素数量均不足 k 个。

提示：

  • n == nums.length
  • 1 <= n <= 10^5
  • 0 <= nums[i], k <= 10^5

解题思路

这道题要求计算每个位置为中心、半径为 k 的子数组的平均值。关键在于高效地计算子数组的和。

思路分析：

  1. 暴力解法：对每个有效位置，直接计算半径为 k 的子数组和，时间复杂度 O(n×k)，可能超时。

  2. 前缀和优化：使用前缀和数组预处理，可以在 O(1) 时间内计算任意区间和。

    • 对于中心位置 i，需要计算区间 [i-k, i+k] 的和
    • 区间和 = prefix[i+k+1] - prefix[i-k]
    • 子数组长度为 2k+1，平均值 = 区间和 / (2k+1)

  3. 滑动窗口优化：维护一个长度为 2k+1 的滑动窗口，逐步移动窗口计算和。

    • 初始化第一个有效窗口的和
    • 向右移动时，减去左边离开的元素，加上右边新进入的元素

推荐解法：滑动窗口，因为它避免了前缀和的额外空间，且代码更简洁。

需要注意的边界条件：

  • 位置 i 有效当且仅当 i-k >= 0 且 i+k < n
  • 使用 long 类型避免整数溢出

代码实现

class Solution {
public:
    vector<int> getAverages(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> result(n, -1);
        
        if (2 * k + 1 > n) {
            return result;
        }
        
        // 计算第一个有效窗口的和
        long long sum = 0;
        for (int i = 0; i < 2 * k + 1; i++) {
            sum += nums[i];
        }
        
        // 第一个有效位置
        result[k] = sum / (2 * k + 1);
        
        // 滑动窗口
        for (int i = k + 1; i < n - k; i++) {
            sum = sum - nums[i - k - 1] + nums[i + k];
            result[i] = sum / (2 * k + 1);
        }
        
        return result;
    }
};

class Solution:
    def getAverages(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        result = [-1] * n
        
        if 2 * k + 1 > n:
            return result
        
        # 计算第一个有效窗口的和
        window_sum = sum(nums[:2 * k + 1])
        
        # 第一个有效位置
        result[k] = window_sum // (2 * k + 1)
        
        # 滑动窗口
        for i in range(k + 1, n - k):
            window_sum = window_sum - nums[i - k - 1] + nums[i + k]
            result[i] = window_sum // (2 * k + 1)
        
        return result

public class Solution {
    public int[] GetAverages(int[] nums, int k) {
        int n = nums.Length;
        int[] result = new int[n];
        Array.Fill(result, -1);
        
        if (2 * k + 1 > n) {
            return result;
        }
        
        // 计算第一个有效窗口的和
        long sum = 0;
        for (int i = 0; i < 2 * k + 1; i++) {
            sum += nums[i];
        }
        
        // 第一个有效位置
        result[k] = (int)(sum / (2 * k + 1));
        
        // 滑动窗口
        for (int i = k + 1; i < n - k; i++) {
            sum = sum - nums[i - k - 1] + nums[i + k];
            result[i] = (int)(sum / (2 * k + 1));
        }
        
        return result;
    }
}

var getAverages = function(nums, k) {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    
    if (2 * k + 1 > n) {
        return result;
    }
    
    // 计算第一个有效窗口的和
    let sum = 0;
    for (let i = 0; i < 2 * k + 1; i++) {
        sum += nums[i];
    }
    
    // 第一个有效位置
    result[k] = Math.floor(sum / (2 * k + 1));
    
    // 滑动窗口
    for (let i = k + 1; i < n - k; i++) {
        sum = sum - nums[i - k - 1] + nums[i + k];
        result[i] = Math.floor(sum / (2 * k + 1));
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度滑动窗口解法前缀和解法
时间复杂度O(n)O(n)
空间复杂度O(1)O(n)

相关题目