前缀和-所有奇数长度子数组的和

题目链接：https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays
题目描述：
给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。
子数组 定义为原数组中的一个连续子序列。
请你返回 arr 中 所有奇数长度子数组的和 。

题解：
方法一：暴力法

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr)
    {
        int len = arr.size();
        if(len == 0)
            return 0;
        int sum = 0;
        for(int i = 1; i <= len; i += 2)      //遍历奇数长度
        {
            for(int j = 0; j < len - i + 1; j++)   //遍历每个长度相同的子数组
            {
                for(int k = 0; k < i; k++)          //遍历每个长度相同的子数组的元素
                {
                    sum += arr[k + j];
                }
            }
        }
        return sum;
    }                                                     
};

方法二：前缀和

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr)
    {
        vector<int> prefixSum(arr.size() + 1, 0);
        int sum = 0;
        for(int i = 0; i < arr.size(); i++)     //前缀和数组
        {
            prefixSum[i + 1] = prefixSum[i] + arr[i];
        }
       
        for(int start = 0; start < arr.size(); start++)                 //子数组开始位置
        {
            for(int len = 1; start + len <= arr.size(); len = len + 2)  //奇数子数组
            {
                int end = start + len - 1;
                sum += prefixSum[end + 1] - prefixSum[start];
            }
        } 
        return sum;            
    }                         
};