题目

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。

子数组 定义为原数组中的一个连续子序列。

请你返回 arr 中 所有奇数长度子数组的和 。

题解

这道题的难点在于 奇数数组的生成，求和的话，可以使用Math.sum(...array)

解法1： 暴力生成

数组长度为n, 子数组开始下标start,结束下标end

则: 0 <= start <= end < n, length = end - start + 1 为奇数, 则为一个奇数子数组, 得到 start和end之后，求和。

遍历, 得到所有子数组的和。

代码:

/**
 * @param {number[]} arr
 * @return {number}
 */
var sumOddLengthSubarrays = function(arr) {
    let length = arr.length
    let sum = 0
    for(let start=0;start<length;start++){
        for(let subLength=1;start+subLength<=length; subLength+=2){
            const end = start+subLength-1;
            for(let i=start;i<=end;i++){
                sum += arr[i]
            }
        }
    }
    return sum
};

前缀和

使用前缀和，来降低子数组求和的时间复杂度。

前缀和数组: prefixSums[0] = 0，当 时，prefixSums[i] 表示数组 arr 从下标 0 到下标 i - 1 的元素和。

数组 start 到 end 的 和: prefixSum[end+1] - prefixSum[start]

代码

/**
 * @param {number[]} arr
 * @return {number}
 */
var sumOddLengthSubarrays = function(arr) {
    let length = arr.length
    let sum  =0

    // 前缀和
    const prefixSum = new Array(length+1).fill(0)
    for(let i=0;i<length;i++){
        prefixSum[i+1] = prefixSum[i] +  arr[i]
    }
    for(let start=0;start<length;start++){
        for(let subLength=1;start+subLength<=length; subLength+=2){
            const end = start+subLength;
            sum += prefixSum[end] - prefixSum[start]
        }
    }
    return sum
};

参考资料

1. 1588. 所有奇数长度子数组的和 (opens new window)
2. 官方题解 (opens new window)