LeetCode 1588. 所有奇数长度子数组的和
目录
题目描述
题意分析
给定一个正整数数组，要把所有长度为奇数的连续子数组各自求和，再把这些和全部加起来返回。注意统计对象是子数组（连续）而不是子序列，长度为 1 的子数组也算奇数长度，必须计入。
数组长度上限是 100，元素值上限是 1000。这个规模其实非常宽松——$O(n^3)$ 的三重循环也只有 $10^6$ 次操作，能过。但题目的进阶要求明确写着「你可以设计一个 $O(n)$ 时间复杂度的算法解决此问题吗」，所以真正被考察的是线性做法。
元素全为正数，所以不存在正负抵消，答案单调随规模增长。总和的量级估算：子数组总数是 $O(n^2)$，每个子数组的和最大约 $10^5$，粗略上界在 $10^8$ 左右，
int装得下，但中间乘法用 64 位更保险。边界上，长度为 1 的数组答案就是它唯一的元素；长度为 2 时只有两个长度为 1 的子数组，答案是两元素之和，长度为 2 的那个子数组不计。
解法：贡献计数
核心思路
枚举所有子数组至少需要 $O(n^2)$。要做到线性时间，应改为计算每个元素对最终答案贡献了多少次。
固定下标
i。包含arr[i]的子数组，左端点有left = i + 1种选择，右端点有right = n - i种选择，共left × right个。子数组长度为奇数，当且仅当左右端点相对
i形成的两段长度奇偶性相同。奇数长度段的选择数分别为(left + 1) / 2、(right + 1) / 2，偶数长度段的选择数分别为left / 2、right / 2，所以arr[i]出现在奇数长度子数组中的次数为：
oddCount = ceil(left/2) × ceil(right/2) + floor(left/2) × floor(right/2)。用整数运算可进一步写成
(left * right + 1) / 2。当乘积为偶数时两类奇偶组合各占一半；乘积为奇数时“同奇”比另一类多一个。不变量：遍历完下标
0..i后，answer等于这些元素在所有奇数长度子数组中的贡献总和。正确性：每个奇数长度子数组中的每个元素，恰好在对应元素的端点组合中被统计一次；不同元素的贡献相加，既不遗漏任何子数组元素，也不会重复计算同一份贡献。因此累加
arr[i] * oddCount得到目标总和。
解题步骤
- 遍历每个下标
i，计算左端点数i + 1与右端点数n - i。- 用
(left * right + 1) / 2得到包含该元素的奇数长度子数组数量。- 将该数量乘以
arr[i]并累加。对
arr = [1,4,2,5,3]，五个位置对应的出现次数为[3,4,5,4,3]，贡献为3 + 16 + 10 + 20 + 9 = 58。长度为 1 时，唯一元素的左右选择数都是 1，出现次数为 1；长度为 2 时两个位置的次数都为 1，因此只统计两个单元素子数组。
代码实现
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)$，只使用固定数量的标量。
关键点总结
- 求所有子数组的总量时，贡献法可以把“枚举区间”改成“枚举元素”。
- 包含下标
i的子数组数由左右端点选择数相乘得到。- 奇数长度对应两侧长度奇偶性相同，计数可化简为
(left * right + 1) / 2。- Java 中间乘法使用
long，避免把公式迁移到更大约束时溢出。
易错点总结
- 直接使用
left * right：会把偶数长度子数组也统计进去。- 把同奇、同偶写成交叉组合：交叉奇偶对应的是偶数长度子数组。
- 左侧写成
i或右侧写成n - i - 1：都会漏掉端点等于i的合法子数组。- 把子数组当成子序列：端点之间必须连续，不能按任意元素组合计数。
- 只统计长度大于 1：单元素子数组长度为 1，也必须计入。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 907. 子数组的最小值之和 | 中等 | 贡献次数由单调栈找出的左右边界决定，而非简单的下标算术 |
| 828. 统计子串中的唯一字符 | 困难 | 按字符的相邻出现位置划分贡献区间，同属「换成逐元素计数」的思路 |
| 1523. 在区间范围内统计奇数数目 | 简单 | 同样用整数除法的取整技巧一次性处理奇偶，得到 $O(1)$ 闭式 |
| 1524. 和为奇数的子数组数目 | 中等 | 同为子数组加奇偶约束，但要靠前缀和奇偶配对而不是贡献计数 |
| 238. 除了自身以外数组的乘积 | 中等 | 同样把每个位置的答案拆成左右两侧的独立量再合并 |
| 560. 和为 K 的子数组 | 中等 | 子数组计数的哈希前缀和范式，与贡献法形成两条不同的降维路线 |
| 1685. 有序数组中差绝对值之和 | 中等 | 靠前缀和把每个位置的两两求和拆成左右两段的闭式，同为拆贡献 |