LeetCode 1588. 所有奇数长度子数组的和
题目描述
题意分析
对每个长度为奇数的连续子数组求元素和，再把这些和全部相加。一个元素可能出现在很多个合法子数组中，每出现一次就贡献一次自己的值。
与其枚举子数组，可以交换求和顺序：逐个统计每个元素被多少个奇数长度子数组包含，再乘上元素值累加。这样能直接做到题目进阶要求的线性时间。
解法：贡献计数
核心思路
[!blue]
固定下标
i，包含它的子数组左端点可选0..i，共有left = i + 1种；右端点可选i..n - 1，共有right = n - i种。左右端点独立决定一个唯一子数组，总共有left * right种组合。设左端点到
i的长度为a，i到右端点的长度为b，两段都包含i，所以完整长度为a + b - 1。它为奇数当且仅当a、b同为奇数或同为偶数。若
left、right至少有一个为偶数，对应一侧的奇偶长度数量相等，无论另一侧怎样选择，恰好一半组合同奇偶。若两者都是奇数，两侧都各多一个奇数长度，同奇偶组合就比异奇偶组合多一个。因此合法数量统一为总组合数的一半向上取整，即(left * right + 1) / 2。将这个数量乘以
arr[i]，就得到当前位置的全部贡献。每个合法子数组中的每个元素都按它自己的位置被计入一次，累加所有位置后与逐个子数组求和完全相同。
解题步骤
- 遍历每个下标
i，计算left = i + 1、right = n - i。- 通过整数除法计算
oddCount = (left * right + 1) / 2，得到包含当前位置的奇数长度子数组数量。- 将
arr[i] * oddCount加入答案。- 所有位置处理完后返回总和，单元素子数组已经自然包含在计数中。
代码实现
class Solution {
public int sumOddLengthSubarrays(int[] arr) {
long answer = 0;
int n = arr.length;
for (int i = 0; i < n; i++) {
// 左、右端点选择数分别为当前位置左侧含自身与右侧含自身的长度。
long left = i + 1L;
long right = n - i;
// 两侧长度同奇偶，总长度才为奇数，合法组合数取乘积的一半向上取整。
long oddCount = (left * right + 1) / 2;
answer += arr[i] * oddCount;
}
return (int) answer;
}
}
func sumOddLengthSubarrays(arr []int) int {
answer := 0
n := len(arr)
for i, value := range arr {
// 左、右端点选择数分别为当前位置左侧含自身与右侧含自身的长度。
left, right := i+1, n-i
// 两侧长度同奇偶，总长度才为奇数，合法组合数取乘积的一半向上取整。
oddCount := (left*right + 1) / 2
answer += value * oddCount
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$，每个元素计算一次贡献。
- 空间复杂度：$O(1)$，只保存累加值。
关键点总结
[!green]
- 按元素贡献求和，避免反复扫描相互重叠的子数组。
- 左右两段都包含当前位置，因此合并长度为
a + b - 1，奇数长度对应两侧同奇偶。- 同奇偶组合占总组合数的一半向上取整，最终公式只需常数次运算。
易错点总结
[!yellow]
- 左右选择数都包含当前位置，分别是
i + 1、n - i，不能漏掉端点。- 两侧长度应同奇偶；若写成异奇偶，统计到的会是偶数长度子数组。
- 总组合数可能为奇数，直接除二会少计一个，需要先加一再做整数除法。
- 出现次数还要乘上当前元素值，只加次数并不是题目要求的总和。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 907. 子数组的最小值之和 | 中等 | 同样改为按每个位置计算贡献，本题统计包含它的奇数长度区间数，而非最小值控制范围。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！