1588. 所有奇数长度子数组的和 - 力扣（LeetCode） (leetcode-cn.com)

1.算法

     暴力解法 复杂度 O(n^3)

     前缀和优化  复杂度O (n^2);

     数学方法     复杂度O(n);

     数学方法公式推导： 

     对于下标为 i 的 项， 包含i 项的子数组有以下情况：

         1. 前边偶数个+ 1                                [ i / 2 ]   (这个符号说明向下取整）

         2.右边偶数个+1                                 [ (n-i-1)/2 ]  

         3 .左边偶数个+1+右边偶数个            [ (i+1)/2 ] * [  (n-i) /2 ]

         4.左边奇数个+1+ 右边奇数个            [ i/2 ]  * [ (n-i-1)/2 ]           

         5. 它自身                                             1

2. 出现向下取整运算的注意！！

      对于上边总结的五种情况 如果使用代码： 

      sum=i/2+(n-i-1)/2 +(i+1)/2*(n-i)/2 +(i/2)*(n-i-1)/2 +1; 

     就会出现错误，可能因为编译器的优化会将一些项合并，取整的含义被优化消失了

     因此应该将每一项单独运算再相加，或者用int （） 将每一次向上取整项括起来。

3.代码

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        //数学
        int ret=0;
        int n= arr.size();
        for(int i=0;i<n;i++){
            int sum=0;
            if(i>0&&n-i-1>0){
                sum=int(i/2)+int((n-i-1)/2)+int((i+1)/2)*int((n-i)/2)+
                int(i/2)*int((n-i-1)/2)+1;
            }
            if(i==0&&n-i-1>0){
                sum=(n-i-1)/2+1;
            }
            if(i>0&&n-i-1==0)
                sum=i/2+1;
            if(i==0&&n-i-1==0)
                sum=1;
            ret+=sum*arr[i];
        }
        return ret;
    }
};