所有奇数长度子数组的和

O(n^3)解法

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int res = 0;
        int n = arr.length;
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                if((j-i)%2 == 0){
                    for(int k=i;k<=j;k++){
                        res+=arr[k];
                    }
                }
            }
        }
        return res;
    }
}

O(n^2)解法：

利用前缀和提前将[0,i)的和求出来后面取只需要O（1）的时间复杂度

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int res = 0;
        int n = arr.length;
        //前缀和，[0,i)
        int []preSum = new int[n+1];
        preSum[0] = 0;
        for(int i=1;i<=n;i++){
            preSum[i] += preSum[i-1]+arr[i-1];
        }
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                if((j-i)%2 == 0){
                    res += preSum[j+1] - preSum[i]; 
                }
            }
        }
        return res;
    }
}

此题有O（n）时间复杂度的解法，是数学找规律的方法：https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays/solution/tong-ji-yuan-su-chu-xian-ci-shu-yi-ci-bian-li-0mss/