题目描述

官方描述(中文)
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.