本文共 676 字，大约阅读时间需要 2 分钟。

题目地址：

给定一个长$n$的数组$A$，求其所有长奇数的子数组的和的总和。

先算前缀和，这样可以$O(1)$询问子数组和了。接着两层循环枚举即可，外层枚举子数组长度，内层枚举左端点。代码如下：

public class Solution {
       public int sumOddLengthSubarrays(int[] arr) {
           int[] preSum = new int[arr.length + 1];        for (int i = 0; i < arr.length; i++) {
               preSum[i + 1] = preSum[i] + arr[i];        }                int res = 0;        for (int i = 1; i <= arr.length; i += 2) {
           	// 右端点要小于arr.length            for (int j = 0; j + i - 1 < arr.length; j++) {
                   res += preSum[j + i] - preSum[j];            }        }                return res;    }}

时间复杂度$O(n^2)$，空间$O(n)$。

转载地址：http://ubjs.baihongyu.com/