1.题目基本信息

1.1.题目描述

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

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

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

1.2.题目地址

https://leetcode.cn/problems/sum-of-all-odd-length-subarrays/description/

2.解题方法

2.1.解题思路

数学方法思路：

• 计算每个arr[i]出现在的合法数组个数，记arr[i]左边有leftCount=i个元素，arr[i]右边有rightCount=n-i-1个元素；由于合法子数组长度为奇数，arr[i]所在合法数组中左边和右边的元素个数要么全是偶数，要么全是奇数。

• 当arr[i]所在合法数组左右个数都是奇数时，左侧的奇数个数leftOdd=(leftCount+1)//2，右侧奇数个数rightOdd=(rightCount+1)//2。当arr[i]所在合法数组的左右个数都是偶数时，左侧偶数个数leftEven=leftCount//2+1，右侧偶数的个数rightEven=rightCount//2+1。

• arr[i]所在的合法数组个数为leftOddrightOdd+leftEvenrightEvent，最后累加结果即为题解

2.2.解题步骤

前缀和方法步骤

• 第一步，构建arr的前缀和数组preSumArr，使求子数组和的时间复杂度降到O(1)

• 第二步，枚举所有合法子数组，求所有合法子数组的和

3.解题代码

前缀和方法代码

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        # 思路1：前缀和
        n = len(arr)
        # 第一步，构建arr的前缀和数组preSumArr，使求子数组和的时间复杂度降到O(1)
        preSumArr = [0] * (n + 1)
        for i in range(n):
            preSumArr[i + 1] = preSumArr[i] + arr[i]
        # 第二步，枚举所有合法子数组，求所有合法子数组的和
        result = 0
        for length in range(1, n + 1, 2):
            i = 0
            while i + length < n + 1:
                sum_ = preSumArr[i + length] - preSumArr[i]
                result += sum_
                i += 1
        return result

数学方法代码

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        # 思路2：数学。计算每个arr[i]出现在的合法数组个数，记arr[i]左边有leftCount=i个元素，arr[i]右边有rightCount=n-i-1个元素；由于合法子数组长度为奇数，arr[i]所在合法数组中左边和右边的元素个数要么全是偶数，要么全是奇数。当arr[i]所在合法数组左右个数都是奇数时，左侧的奇数个数leftOdd=(leftCount+1)//2，右侧奇数个数rightOdd=(rightCount+1)//2。当arr[i]所在合法数组的左右个数都是偶数时，左侧偶数个数leftEven=leftCount//2+1，右侧偶数的个数rightEven=rightCount//2+1。arr[i]所在的合法数组个数为leftOdd*rightOdd+leftEven*rightEvent，最后累加结果即为题解
        n = len(arr)
        result = 0
        for i in range(n):
            leftCount, rightCount = i, n - i - 1
            leftOdd = (leftCount + 1) // 2
            rightOdd = (rightCount + 1) // 2
            leftEven = leftCount // 2 + 1
            rightEven = rightCount // 2 + 1
            result += arr[i] * (leftOdd * rightOdd + leftEven * rightEven)
        return result

4.执行结果