§1
题目描述
给你一个正整数数组 arr，请你计算所有可能的奇数长度子数组的和。子数组定义为原数组中的一个连续子序列。
输入 = arr = [1,4,2,5,3]
输出 = 58
解释 = 长度为 1 的子数组和为 15；长度为 3 的子数组和为 36；长度为 5 的子数组和为 7；总和为 58。
输入 = arr = [1,2]
输出 = 3
§2
思路解析动画文字版
比如 arr[2]=2 会出现在多个奇数长度子数组里。与其重复枚举子数组，不如直接数它出现了几次。
于是 arr[i] 对答案的贡献就是 arr[i] * odd。把每个位置的贡献加起来，就是所有奇数长度子数组的总和。
初始化：准备按位置计算贡献：ans 不是一次加一个子数组，而是一次加一个元素的总贡献。
先看公式来源：固定 arr[2] = 2：包含下标 2 的子数组，左边界可选 0、1、2，右边界可选 2、3、4。9 个组合里有 5 个是奇数长度。
i=0，x=1：1 会出现在 3 个奇数长度子数组里：[1]、[1,4,2]、[1,4,2,5,3]，贡献 3。
i=1，x=4：4 被 4 个奇数长度子数组包含，贡献 16。ans 从 3 变成 19。
i=2，x=2：中间元素被包含的组合最多。这里 2 出现在 5 个奇数长度子数组里，贡献 10。
i=3，x=5：靠右的位置，左边界选择变多，右边界选择变少；乘起来还是 total=8。
i=4，x=3：最后一个元素也会出现在 3 个奇数长度子数组里，贡献 9。总答案来到 58。
返回答案：这和逐个枚举奇数长度子数组得到的 58 完全一致，但代码只扫了一次数组。
以后看到“所有子数组的总和/最小值/最大值之和”，都可以先想一想能不能按元素贡献来算。
§3
参考代码
class Solution: def sumOddLengthSubarrays(self, arr): n = len(arr) ans = 0 for i, x in enumerate(arr): total = (i + 1) * (n - i) odd = (total + 1) // 2 ans += x * odd return ans看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。
§4
复杂度
- 时间复杂度：O(n)，每个元素只计算一次贡献。
- 空间复杂度：O(1)，只使用 n、ans、total、odd 等常数个变量。
§5
易错点
✗ 错误写法：把子序列当成子数组
✓ 正确写法：子数组必须连续
题目里的 subarray 是连续片段，不是任意挑元素。
✗ 错误写法：只把 odd 加进答案
✓ 正确写法：要加 x * odd
odd 是出现次数，真正贡献还要乘当前位置的值。
✗ 错误写法：把奇数次数写成 total // 2
✓ 正确写法：写成 (total + 1) // 2
当 total 为奇数时，奇数长度子数组会多一个。
✗ 错误写法：只会枚举子数组
✓ 正确写法：学会从元素贡献反推答案
贡献法是很多子数组求和题的高阶入口。
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
下一题 · 数组套路 7/12
→下一个排列
LeetCode 31 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
299道动画图解
37节语音讲解
28课数据结构
¥0.27折合 / 天
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
¥99 开通年卡 →
想成体系刷透这类套路？去图解算法专题