题目描述
官方描述(中文)
2021/08/29每日一题
思路
三层暴力
第一种暴力方法使用三层for循环进行结果求取。
第一层:奇数子序列的第一个数字的位置
第二层:奇数子序列最后一个数字的个数
第三层:首部与尾部加和
代码
class Solution
{
public:
int sumOddLengthSubarrays(vector<int>& arr)
{
int res = 0;
for(int i = 0; i< arr.size(); ++i)
{
//j每次加2保证i到j的个数是奇数
for(int j = i; j<arr.size(); j+=2)
{
for(int k = i; k<=j; ++k)
{
res+=arr[k];
}
}
}
return res;
}
};
执行结果
前缀和
通过上面的暴力破解,我们发现其实第三层循环是可以通过前缀和来进行优化的,因为第三层每次都会重复计算i到j之间数字的和,如果我们提前计算好,就可省去这一步。
代码
class Solution
{
public:
int sumOddLengthSubarrays(vector<int>& arr)
{
int n = arr.size();
vector<int> prefix(n+1, 0);
//前缀和求取
for (int i = 0; i < n; i++)
{
prefix[i + 1] = prefix[i] + arr[i];
}
int res = 0;
for (int i = 0; i < n; i++) //子序列起始位置
{
for (int j = i; j < n; j += 2) //子序列结束位置
{
res += prefix[j+1] - prefix[i];
}
}
return res;
}
};
执行结果
Q.E.D.