给你一个正整数数组 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 <= 1001 <= arr[i] <= 1000
进阶:
你可以设计一个 O(n) 时间复杂度的算法解决此问题
解题思路
前缀和
暴力做起来很麻烦。求数组连续子序列之和,那我们先试试前缀和。
首先是每个元素相加,这个没什么问题。问题在于如何处理前缀和。我们可以从样例一入手。从i=3开始,前缀和的规律是
- result=sum[3]-0
- result=sum[4]-sum[1]
- result=sum[5]-sum[2]
当i=5时
- result=sum[5]-0
- result=sum[6]-sum[1] (如果有的话)
- …
那写个双for完事了。至于进阶里提到的O(n)解决该问题,鉴定为纯纯的数学题,和前缀和没啥关系,所以就不看了。
class Solution {
public:
int sumOddLengthSubarrays(vector<int>& arr) {
int size=arr.size();
vector<int>sum;
sum.resize(size+1);
int result=0;
for(int i=0;i<size;i++)
{
sum[i+1]=sum[i]+arr[i];
result+=arr[i];
}
for(int i=3;i<=size;i+=2)
{
for(int j=i;j<=size;j++)
{
result+=sum[j]-sum[j-i];
}
}
return result;
}
};