leetcode1588 前缀和

暴力枚举

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

这种算法是将示例中的【1，4，2，5，3】得到1然后得到1 4 2 在得到1 4 2 5 3，再进行下一个4的遍历，中间的for就是控制次数，最外层遍历一次数，最里层加值。

前缀和：

class Solution {public int sumOddLengthSubarrays(int[] arr) {int [] qianzhui=new int[arr.length+1];for(int i=0;i<arr.length;i++){qianzhui[i+1]=arr[i]+qianzhui[i];}int res=0;for(int i=0;i<arr.length;i++){for(int j=1;i+j<=arr.length;j+=2){res+=qianzhui[i+j]-qianzhui[i];}}
return res;}
}

暴力法的时间是O(n^3) 我们用前缀和的方法相当于把暴力法中的最内层的for循环拿出来，用之前的数组写一个前缀和的数组即可将时间复杂度降到O（n^2）.