1588. 所有奇数长度子数组的和.md

1588. 所有奇数长度子数组的和

• 时间复杂度O(n * n),空间复杂度O(1)

/**
 * @param {number[]} arr
 * @return {number}
 */
var sumOddLengthSubarrays = function (arr) {
    arr = getPrefixSum(arr);
    return getOddSum(arr);
};

// 获取前缀和
function getPrefixSum(array) {
    for (let i = 1; i < array.length; ++i) {
        array[i] += array[i - 1];
    }
    return array;
}

// 已知前缀和,获取所有奇数长度子数组的和
function getOddSum(prefixSumArray) {
    let sum = 0;
    for (let i = 0; i < prefixSumArray.length; ++i) {
        for (let j = i; j >= 0; j -= 2) {
            sum += (j === 0) ? prefixSumArray[i] : prefixSumArray[i] - prefixSumArray[j - 1];
        }
    }
    return sum;
}

• 时间复杂度O(n),空间复杂度O(1)

/**
 * @param {number[]} arr
 * @return {number}
 */
var sumOddLengthSubarrays = function (arr) {
    let sum = 0;
    for (let i = 0; i < arr.length; ++i) {
        const leftNumber = i,
            rightNumber = arr.length - i - 1,
            leftOdd = Math.ceil(leftNumber / 2),
            leftEven = Math.floor(leftNumber / 2) + 1,
            rightOdd = Math.ceil(rightNumber / 2),
            rightEven = Math.floor(rightNumber / 2) + 1;
        sum += (leftOdd * rightOdd + leftEven * rightEven) * arr[i];
    }
    return sum;
};