难度: Easy
给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。
子数组 定义为原数组中的一个连续子序列。
请你返回 arr 中 所有奇数长度子数组的和 。
示例 1：
输入：arr = [1,4,2,5,3] 输出：58 解释：所有奇数长度子数组和它们的和为： [1] = 1 [4] = 4 [2] = 2 [5] = 5 [3] = 3 [1,4,2] = 7 [4,2,5] = 11 [2,5,3] = 10 [1,4,2,5,3] = 15 我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58
示例 2：
输入：arr = [1,2] 输出：3 解释：总共只有 2 个长度为奇数的子数组，[1] 和 [2]。它们的和为 3 。
示例 3：
输入：arr = [10,11,12] 输出：66
提示：
1 <= arr.length <= 1001 <= arr[i] <= 1000进阶：
你可以设计一个 O(n) 时间复杂度的算法解决此问题吗？
运行时间: 20 ms
内存: 16.0 MB
class Solution:
def sumOddLengthSubarrays(self, arr: List[int]) -> int:
final = 0
left_sum = [0] * (len(arr) + 1)
for i in range(len(arr)):
left_sum[i + 1] = left_sum[i] + arr[i]
for i in range(len(arr)):
now_len = 1
while i + now_len <= len(arr):
now_sum = left_sum[i + now_len] - left_sum[i]
final += now_sum
now_len += 2
return final
该题解采用前缀和和滑动窗口的思路。首先，计算原数组的前缀和数组left_sum，使得left_sum[i]表示原数组arr中前i个元素的和。然后，对于原数组中的每个元素arr[i]，通过滑动窗口的方式计算以arr[i]为起始元素的所有奇数长度子数组的和，并累加到最终结果final中。具体而言，对于每个起始元素arr[i]，窗口长度now_len从1开始，每次增加2，直到窗口超出数组边界。在每个窗口内，计算子数组的和now_sum为left_sum[i + now_len] - left_sum[i]，然后将now_sum累加到final中。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def sumOddLengthSubarrays(self, arr: List[int]) -> int:
final = 0 # 最终结果
left_sum = [0] * (len(arr) + 1) # 前缀和数组
# 计算前缀和
for i in range(len(arr)):
left_sum[i + 1] = left_sum[i] + arr[i]
# 计算所有奇数长度子数组的和
for i in range(len(arr)):
now_len = 1 # 当前窗口长度
while i + now_len <= len(arr):
now_sum = left_sum[i + now_len] - left_sum[i] # 当前窗口内子数组的和
final += now_sum
now_len += 2
return final
使用前缀和的主要优势是其能极大地优化求连续子数组和的操作。如果直接在数组上迭代求每个奇数长度子数组的和，每次计算都需要线性时间遍历子数组，导致整体时间复杂度较高。而通过前缀和数组，我们可以在常数时间内得到任何子数组的和，从而显著减少了重复计算，提高了算法效率。
常见的滑动窗口方法通常用于处理固定长度或最大长度限制的连续子数组问题，窗口大小一般会动态调整但通常是连续滑动。在本题中，滑动窗口的长度始终为奇数，且每次增长步长为2，这是为了专门计算奇数长度的子数组之和。这种使用滑动窗口的方式更加专注于控制子数组的长度，而不仅仅是位置调整。
题目要求计算所有奇数长度子数组的和。因此，窗口长度now_len从1开始，即最短的奇数长度，并且每次增加2来保持窗口长度始终为奇数。如果窗口长度按1或其他非2的间隔增长，那么我们将无法保证窗口长度始终为奇数，从而无法满足题目的要求。
在编程实现时，需要小心处理边界条件。通过确保在计算子数组和时使用的索引不超出数组范围，可以避免越界错误。在题解中，通过条件`i + now_len <= len(arr)`来保证。这个条件确保即使在最大的窗口长度下，子数组的结束索引也不会超过数组的实际长度。