LeetCode 1588简单数组
所有奇数长度子数组的和 图解题解
这道题到底在问什么
给你一个正整数数组 arr，请你计算所有可能的奇数长度子数组的和。子数组定义为原数组中的一个连续子序列。
- 输入
- arr = [1,4,2,5,3]
- 输出
- 58
- 解释
- 长度为 1 的子数组和为 15；长度为 3 的子数组和为 36；长度为 5 的子数组和为 7；总和为 58。
- 输入
- arr = [1,2]
- 输出
- 3
先想最直接的笨办法
比如 arr[2]=2 会出现在多个奇数长度子数组里。与其重复枚举子数组，不如直接数它出现了几次。（动画第 3 步）
最优解：一步一步想明白
- 3比如 arr[2]=2 会出现在多个奇数长度子数组里。与其重复枚举子数组，不如直接数它出现了几次。
- 4于是 arr[i] 对答案的贡献就是 arr[i] * odd。把每个位置的贡献加起来，就是所有奇数长度子数组的总和。
- 5n = len(arr); ans = 0ans 不是一次加一个子数组，而是一次加一个元素的总贡献。
- 6公式推导：先理解 total 和 odd 的来源包含下标 2 的子数组，左边界可选 0、1、2，右边界可选 2、3、4。9 个组合里有 5 个是奇数长度。
- 7total = (i + 1) * (n - i); odd = (total + 1) // 2; ans += x * odd1 会出现在 3 个奇数长度子数组里：[1]、[1,4,2]、[1,4,2,5,3]，贡献 3。
- 8total = (i + 1) * (n - i); odd = (total + 1) // 2; ans += x * odd4 被 4 个奇数长度子数组包含，贡献 16。ans 从 3 变成 19。
- 9total = (i + 1) * (n - i); odd = (total + 1) // 2; ans += x * odd中间元素被包含的组合最多。这里 2 出现在 5 个奇数长度子数组里，贡献 10。
- 10total = (i + 1) * (n - i); odd = (total + 1) // 2; ans += x * odd靠右的位置，左边界选择变多，右边界选择变少；乘起来还是 total=8。
- 11total = (i + 1) * (n - i); odd = (total + 1) // 2; ans += x * odd最后一个元素也会出现在 3 个奇数长度子数组里，贡献 9。总答案来到 58。
- 12return ans这和逐个枚举奇数长度子数组得到的 58 完全一致，但代码只扫了一次数组。
- 15以后看到“所有子数组的总和/最小值/最大值之和”，都可以先想一想能不能按元素贡献来算。
⚠️ 容易写错的地方
✗ 错：把子序列当成子数组
✓ 对：子数组必须连续
题目里的 subarray 是连续片段，不是任意挑元素。
✗ 错：只把 odd 加进答案
✓ 对：要加 x * odd
odd 是出现次数，真正贡献还要乘当前位置的值。
✗ 错：把奇数次数写成 total // 2
✓ 对：写成 (total + 1) // 2
当 total 为奇数时，奇数长度子数组会多一个。
✗ 错：只会枚举子数组
✓ 对：学会从元素贡献反推答案
贡献法是很多子数组求和题的高阶入口。
完整代码（Python）
Python
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复杂度
时间复杂度
O(n)
每个元素只计算一次贡献。
空间复杂度
O(1)
只使用 n、ans、total、odd 等常数个变量。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 所有奇数长度子数组的和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「数组」，换最直接的暴力解会差在哪？+
数组抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。