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

Given an array of positive integers arr , calculate the sum of all possible odd-length subarrays.

A subarray is a contiguous subsequence of the array.

Return the sum of all odd-length subarrays of arr .

Example 1:

Input: arr = [1,4,2,5,3]Output: 58Explanation: The odd-length subarrays of arr and their sums are:[1] = 1[4] = 4[2] = 2[5] = 5[3] = 3[1,4,2] = 7[4,2,5] = 11[2,5,3] = 10[1,4,2,5,3] = 15If we add all these together we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

Example 2:

Input: arr = [1,2]Output: 3Explanation: There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3.

Example 3:

Input: arr = [10,11,12]Output: 66

Constraints:

• 1 <= arr.length <= 100
• 1 <= arr[i] <= 1000

题意：统计正整数数组中，所有长度为奇数的子数组的和。

思路1：$O(n^3)$ 的算法，枚举每个子区间的左右端点，如果长度为奇数，则又用一次循环计算它的元素和。这里就不写出来了。

思路2：$O(n^2)$ 的算法，用前缀和去掉上一个思路中的内部循环，第二重循环每次可以 += 2 。代码如下：

class Solution {
   public:    int sumOddLengthSubarrays(vector
   
    & arr) {
           if (arr.size() <= 1) return arr[0];        int ans = 0;        vector
    
      presum(arr.size() + 1);        for (int i = 0; i < arr.size(); ++i) presum[i + 1] = presum[i] + arr[i];        for (int i = 0; i < arr.size(); ++i) {
               for (int j = i; j < arr.size(); j += 2) {
                   int len = j - i + 1;                if (len & 1) ans += presum[j + 1] - presum[i];            }        }        return ans;    }   };
    
   

思路3：其实完全可以不用前缀和，直接模拟就可以了。代码如下：

class Solution {
   public:    int sumOddLengthSubarrays(vector
   
    & arr) {
           if (arr.size() <= 1) return arr[0];        int ans = 0;          for (int i = 0; i < arr.size(); ++i) {
               int sum = 0;            for (int j = i; j < arr.size(); ++j) {
                   sum += arr[j];                if ((j - i + 1) & 1) ans += sum;            }        }        return ans;    }   };
   

转载地址：https://memcpy0.blog.csdn.net/article/details/108710821 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！