LeetCode刷题（174）～所有奇数长度子数组的和【第35场双周赛：题目一 前缀和】

题目描述

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。

子数组 定义为原数组中的一个连续子序列。

请你返回 arr 中 所有奇数长度子数组的和 。

示例 1：

输入：arr = [1,4,2,5,3]
输出：58
解释：所有奇数长度子数组和它们的和为：
[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] = 15
我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

示例 2：

输入：arr = [1,2]
输出：3
解释：总共只有 2 个长度为奇数的子数组，[1] 和 [2]。它们的和为 3 。

  

 

  
1
  
2
  
3
 

示例 3：

输入：arr = [10,11,12]
输出：66

  

 

  
1
  
2
 

提示：

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

解答 By 海轰

提交代码（暴力）

int sumOddLengthSubarrays(vector<int>& arr) { int sum=0; for(int i=1;i<=arr.size();i+=2) { for(int j=0;j<=arr.size()-i;++j) { for(int k=0;k<i;++k) { sum+=arr[j+k]; } } } return sum; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
 

运行结果

提交代码（暴力 accumulate ）

int sumOddLengthSubarrays(vector<int>& arr) { int sum=0; for(int i=0;i<arr.size();++i) { for(int j=1;i+j-1<arr.size();j+=2) sum+= accumulate(arr.begin()+i,arr.begin()+i+j,0); } return sum; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
 

运行结果

提交代码（前缀和）

int sumOddLengthSubarrays(vector<int>& arr) { int sum=0; for(int i=1;i<arr.size();++i) arr[i]+=arr[i-1]; for(int i=0;i<arr.size();++i) { for(int j=1;i+j-1<arr.size();j+=2) { if(i==0) sum+= arr[j-1]; else sum+= arr[i+j-1]-arr[i-1]; } } return sum; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

运行结果

提交代码（前缀和 优化）

class Solution {
public: int sumOddLengthSubarrays(vector<int>& arr) { vector<int> presum = {0};// 注意头部加上0 便于计算 for(int e: arr) presum.push_back(presum.back() + e); int res = 0; for(int i = 0; i < arr.size(); i ++) for(int sz = 1; i + sz - 1 < arr.size(); sz += 2) res += presum[i + sz] - presum[i]; return res; }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
 

提交代码

int sumOddLengthSubarrays(vector<int>& arr) { int sum=0; for(int i=0;i<arr.size();++i) { int left=i+1;//该数左边可以选择数的个数 int right=arr.size()-i;// 右边可选数的个数 int left_even=(left+1)/2;// 左边选数的个数为偶数 int left_odd=left/2;// 左边选数的个数为奇数 int right_even=(right+1)/2;// 右边选的数的个数为偶数 int right_odd=right/2;//右边选的数的个数为奇数 sum+= (left_even*right_even+left_odd*right_odd)*arr[i]; } return sum; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
 

运行结果

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays
思路来源：https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays/solution/cong-on3-dao-on-de-jie-fa-by-liuyubobobo/

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/108694836