所有奇数长度子数组的和 图解题解
这道题到底在问什么
- 输入
- arr = [1,4,2,5,3]
- 输出
- 58
先想最直接的笨办法
思路：按长度 1、3、5 分组枚举，每段算和累加进 total。下面每一帧圈出一段，并把它的和加进 total。（动画第 3 步）
最优解：一步一步想明白
- 3思路：按长度 1、3、5 分组枚举，每段算和累加进 total。下面每一帧圈出一段，并把它的和加进 total。
- 4先看长度为 1 的子数组：左端点从下标 0 开始，每次右移一格，把每一段都圈出来累加。
- 5圈出从下标 0 到 0 这一段（长度 1），它的和是 1 = 1。
- 6把这段的和 1 加进 total，total 变成 1。
- 7圈出从下标 1 到 1 这一段（长度 1），它的和是 4 = 4。
- 8把这段的和 4 加进 total，total 变成 5。
- 9圈出从下标 2 到 2 这一段（长度 1），它的和是 2 = 2。
- 10把这段的和 2 加进 total，total 变成 7。
- 11圈出从下标 3 到 3 这一段（长度 1），它的和是 5 = 5。
- 12把这段的和 5 加进 total，total 变成 12。
- 13圈出从下标 4 到 4 这一段（长度 1），它的和是 3 = 3。
- 14把这段的和 3 加进 total，total 变成 15。
- 15先看长度为 3 的子数组：左端点从下标 0 开始，每次右移一格，把每一段都圈出来累加。
- 16圈出从下标 0 到 2 这一段（长度 3），它的和是 1+4+2 = 7。
- 17把这段的和 7 加进 total，total 变成 22。
- 18圈出从下标 1 到 3 这一段（长度 3），它的和是 4+2+5 = 11。
- 19把这段的和 11 加进 total，total 变成 33。
- 20圈出从下标 2 到 4 这一段（长度 3），它的和是 2+5+3 = 10。
- 21把这段的和 10 加进 total，total 变成 43。
- 22先看长度为 5 的子数组：左端点从下标 0 开始，每次右移一格，把每一段都圈出来累加。
- 23圈出从下标 0 到 4 这一段（长度 5），它的和是 1+4+2+5+3 = 15。
- 24把这段的和 15 加进 total，total 变成 58。
- 25长度 1、3、5 的所有段都累加完了，total = 58 就是最终答案。
⚠️ 容易写错的地方
✗ 错：把长度从 1 开始每次只加 1（1,2,3,…）
✓ 对：长度每次加 2，只取 1,3,5,…
题目只要奇数长度子数组，偶数长度不能算进去
✗ 错：左端点循环写成 s + len < n
✓ 对：条件是 s + len <= n
用 < 会漏掉最右边那一段，比如整个数组那段会被漏算
✗ 错：每段重新从头加和导致超时也没关系？实际数据大时会超时
✓ 对：数据大时改用前缀和或数学公式
n 很大时 O(n³) 会超时，前缀和让每段求和变 O(1)
完整代码（Python / C++ / Java）
Python
def sumOddLengthSubarrays(arr):
n = len(arr)
total = 0
length = 1 # 只取奇数长度
while length <= n:
s = 0 # 左端点
while s + length <= n:
total += sum(arr[s:s+length])
s += 1
length += 2 # 1,3,5,...
return totalC++
int sumOddLengthSubarrays(vector<int>& arr){
int n = arr.size(), total = 0;
for (int len = 1; len <= n; len += 2) {
for (int s = 0; s + len <= n; s++) {
int sum = 0;
for (int k = s; k < s + len; k++) sum += arr[k];
total += sum;
}
}
return total;
}Java
public int sumOddLengthSubarrays(int[] arr) {
int n = arr.length, total = 0;
for (int len = 1; len <= n; len += 2) {
for (int s = 0; s + len <= n; s++) {
int sum = 0;
for (int k = s; k < s + len; k++) sum += arr[k];
total += sum;
}
}
return total;
}复杂度
时间
O(n³)
枚举长度与左端点是 O(n²) 段，每段再求和是 O(n)，朴素枚举共 O(n³)
空间
O(1)
只用 total 一个累加器和几个循环变量，不开额外数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 所有奇数长度子数组的和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么长度从 1 开始、每次加 2？+
题目只要奇数长度的子数组，奇数就是 1,3,5,…，所以起点 1、步长 2，正好枚举全部奇数长度，且不超过数组长度 n。
这个朴素解法的时间复杂度是多少？能优化吗？+
朴素三重循环是 O(n³)。用前缀和把每段求和降到 O(1) 后是 O(n²)；更进一步，可以推导「每个元素出现在多少个奇数长度子数组里」的公式，做到 O(n)。
怎么算一个元素被多少个奇数长度子数组包含？+
下标 i 的元素，左边可选端点有 i+1 个、右边有 n-i 个，总子数组数 left*right；其中奇数长度的数量约为 (left*right+1)//2，乘以该元素的值再累加即得答案。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 所有奇数长度子数组的和 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。