1588. 所有奇数长度子数组的和：
给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。
子数组 定义为原数组中的一个连续子序列。
请你返回 arr 中 所有奇数长度子数组的和 。
样例 1
输入：
arr = [1,4,2,5,3]
输出：
58
解释：
所有奇数长度子数组和它们的和为：
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58
样例 2
输入：
arr = [1,2]
输出：
3
解释：
总共只有 2 个长度为奇数的子数组，[1] 和 [2]。它们的和为 3 。
样例 3
输入：
arr = [10,11,12]
输出：
66
提示
- 1 <= arr.length <= 100
- 1 <= arr[i] <= 1000
分析
- 这道算法题的题意应该不难理解，暴力O(n3)的解法应该都能想到。
- 有人会想到用滑动窗口或者前缀和，这些是常用的优化手段。
- 根据题意我们知道子数组就像子序列，是否出现在子数组中，和数字具体是多少无关，只和位置有关。
- 既然和具体数字无关，这种子序列，子数组，排列组合，就一定有规律，可以用数学的方式去解决。
- 我们可以一头到尾遍历一遍，然后累加 每个数字的值乘以每个数字出现在子数组的次数 就可以得到结果。接下来就变成我们是否可以找到每个数字出现在子数组中的次数规律。
- 假设我们选定一个数字，那么除了这个数字之外，我们还可以另外选择 偶数个其他数字 凑成奇数长度的子数组。
- 我们可以把其他数字的选择，分成左面和右面两部分，那么这个选定的数字出现在子数组的次数就是 左面可选数字方案数 * 右面数字可选方案数。
- 奇数=1 + 偶数，选定一个数字之后，如果左面选择奇数个数字，那么右面也必须选择奇数个数字；如果左面选择偶数个数字，那么右面也要选择偶数个数字。这样加上选定的数字，就刚好是奇数长度子数组。
- 最终每个数字出现的次数就是 左面选择奇数个数字的方案数 右面选择奇数个数字的方案数 + 左面选择偶数个数字的方案数 右面选择偶数个数字的方案数。
- 从0到n中，奇数的数量是(n + 1) / 2个，偶数的数量是n / 2 + 1（0也算偶数个）。
题解
java
class Solution {
public int sumOddLengthSubarrays(int[] arr) {
int ans = 0;
int endIndex = arr.length - 1;
for (int i = 0; i <= endIndex; ++i) {
int leftCount = i;
int rightCount = endIndex - i;
int leftOdd = (leftCount + 1) / 2;
int rightOdd = (rightCount + 1) / 2;
int leftEven = leftCount / 2 + 1;
int rightEven = rightCount / 2 + 1;
ans += arr[i] * (leftOdd * rightOdd + leftEven * rightEven);
}
return ans;
}
}c
int sumOddLengthSubarrays(int* arr, int arrSize){
int ans = 0;
int endIndex = arrSize - 1;
for (int i = 0; i <= endIndex; i++) {
int leftCount = i;
int rightCount = endIndex - i;
int leftOdd = (leftCount + 1) / 2;
int rightOdd = (rightCount + 1) / 2;
int leftEven = leftCount / 2 + 1;
int rightEven = rightCount / 2 + 1;
ans += arr[i] * (leftOdd * rightOdd + leftEven * rightEven);
}
return ans;
}c++
class Solution {
public:
int sumOddLengthSubarrays(vector<int>& arr) {
int ans = 0;
int endIndex = arr.size() - 1;
for (int i = 0; i <= endIndex; i++) {
int leftCount = i;
int rightCount = endIndex - i;
int leftOdd = (leftCount + 1) / 2;
int rightOdd = (rightCount + 1) / 2;
int leftEven = leftCount / 2 + 1;
int rightEven = rightCount / 2 + 1;
ans += arr[i] * (leftOdd * rightOdd + leftEven * rightEven);
}
return ans;
}
};python
class Solution:
def sumOddLengthSubarrays(self, arr: List[int]) -> int:
ans = 0
endIndex = len(arr) - 1
for i, v in enumerate(arr):
leftCount, rightCount = i, endIndex - i
leftOdd = (leftCount + 1) // 2
rightOdd = (rightCount + 1) // 2
leftEven = leftCount // 2 + 1
rightEven = rightCount // 2 + 1
ans += v * (leftOdd * rightOdd + leftEven * rightEven)
return ans
go
func sumOddLengthSubarrays(arr []int) (ans int) {
endIndex := len(arr) - 1
for i, v := range arr {
leftCount, rightCount := i, endIndex-i
leftOdd := (leftCount + 1) / 2
rightOdd := (rightCount + 1) / 2
leftEven := leftCount/2 + 1
rightEven := rightCount/2 + 1
ans += v * (leftOdd*rightOdd + leftEven*rightEven)
}
return ans
}rust
impl Solution {
pub fn sum_odd_length_subarrays(arr: Vec<i32>) -> i32 {
let endIndex = arr.len() - 1;
arr.iter().enumerate().map(|(i, v)| {
let leftCount = i;
let rightCount = endIndex - i;
let leftOdd = (leftCount + 1) / 2;
let rightOdd = (rightCount + 1) / 2;
let leftEven = leftCount / 2 + 1;
let rightEven = rightCount / 2 + 1;
arr[i] * ((leftOdd * rightOdd + leftEven * rightEven) as i32)
}).sum()
}
}
原题传送门：https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays/
非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~
