---

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

• 标签：数组、数学、前缀和
• 难度：简单

题目链接

• 1588. 所有奇数长度子数组的和 - 力扣

题目大意

描述：给定一个正整数数组 $arr$。

要求：返回所有奇数长度子数组的和。

说明：

• $1 \le arr.length \le 100$。
• $1 \le arr[i] \le 1000$。

示例：

• 示例 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 。

解题思路

思路 1：暴力

1. 核心思想

枚举所有奇数长度的子数组，求和。

$n \le 100$，总子数组数 $n(n+1)/2 \le 5050$，暴力即可。

2. 具体步骤

第 1 步：$ans = 0$。

第 2 步：遍历每个起点 $i$，遍历奇数长度 $len = 1, 3, 5, \dots$：

• 如果是奇数长度且不越界，计算子数组和。

第 3 步：返回 $ans$。

3. 优化：前缀和

先用前缀和 $O(1)$ 计算子数组和。

4. 举例说明

以 $arr = [1,4,2,5,3]$ 为例：

奇数长度子数组：

• 长度 $1$：$[1],[4],[2],[5],[3]$，和 $=15$。
• 长度 $3$：$[1,4,2]=7$，$[4,2,5]=11$，$[2,5,3]=10$，和 $=28$。
• 长度 $5$：$[1,4,2,5,3]=15$。

总 $= 15+28+15=58$。

思路 1：代码

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + arr[i]

        ans = 0
        for length in range(1, n + 1, 2):  # 奇数长度
            for i in range(n - length + 1):
                ans += prefix[i + length] - prefix[i]
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n^2)$。
• 空间复杂度：$O(n)$。