文章目录
- 一【题目类别】
- 二【题目难度】
- 三【题目编号】
- 四【题目描述】
- 五【题目示例】
- 六【题目提示】
- 七【题目进阶】
- 八【解题思路】
- 九【时间频度】
- 十【代码实现】
- 十一【提交结果】
一【题目类别】
- 前缀和
二【题目难度】
- 简单
三【题目编号】
- 1588.所有奇数长度子数组的和
四【题目描述】
- 给你一个正整数数组
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
-
示例 2:
- 输入:arr = [1,2]
- 输出:3
- 解释:总共只有 2 个长度为奇数的子数组,[1] 和 [2]。它们的和为 3 。
-
示例 3:
- 输入:arr = [10,11,12]
- 输出:66
六【题目提示】
1 <= arr.length <= 100
1 <= arr[i] <= 1000
七【题目进阶】
- 你可以设计一个 O ( n ) O(n) O(n) 时间复杂度的算法解决此问题吗?
八【解题思路】
- 该题很容易想到的思路就是暴力模拟,这个方式确实很简单,不过复杂度太高
- 所以使用前缀和方法来解决该问题可以降低时间复杂度
- 计算前缀和数组,前缀和数组的每一位表示从原数组的开始到每一位的累加和
- 然后使用简单的数学运算找到所有奇数长度子数组
- 最后使用前缀和数组对找到的所有奇数长度子数组求和
- 最后返回结果即可
- 具体细节可以参考下面的代码
九【时间频度】
- 时间复杂度: O ( n 2 ) O(n^2) O(n2), n n n为传入的数组的长度
- 空间复杂度: O ( n ) O(n) O(n), n n n为传入的数组的长度
十【代码实现】
- Java语言版
class Solution {public int sumOddLengthSubarrays(int[] arr) {// 计算前缀和数组,prefixSum[i]表示数组arr从索引0到i的累加和int[] prefixSum = new int[arr.length];prefixSum[0] = 0;for (int i = 1; i < arr.length; i++){prefixSum[i] = prefixSum[i - 1] + arr[i];}// 保存结果int sum = 0;// 计算所有奇数长度子数组的和for (int start = 0; start < arr.length; start++){// 计算奇数长度子数组区间的和for (int length = 1; start + length <= arr.length; length += 2){// 计算奇数长度子数组的末尾索引int end = start + length - 1;// 根据前缀和数组计算奇数长度子数组的和sum += prefixSum[end] - prefixSum[start] + arr[start];}}// 返回结果return sum;}
}
- Python语言版
class Solution:def sumOddLengthSubarrays(self, arr: List[int]) -> int:# 计算前缀和数组,prefixSum[i]表示数组arr从索引0到i的累加和prefix_sum = [0] * len(arr)prefix_sum[0] = 0for i in range(1, len(arr)):prefix_sum[i] = prefix_sum[i - 1] + arr[i]# 保存结果res = 0# 计算所有奇数长度子数组的和for start in range(0, len(arr)):# 计算奇数长度子数组区间的和for length in range(1, len(arr) - start + 1, 2):# 计算奇数长度子数组的末尾索引end = start + length - 1# 根据前缀和数组计算奇数长度子数组的和res += prefix_sum[end] - prefix_sum[start] + arr[start]# 返回结果return res
- C语言版
int sumOddLengthSubarrays(int* arr, int arrSize)
{// 计算前缀和数组,prefixSum[i]表示数组arr从索引0到i的累加和int* prefixSum = (int*)malloc(sizeof(int) * arrSize);prefixSum[0] = arr[0];for (int i = 1; i < arrSize; i++){prefixSum[i] = prefixSum[i - 1] + arr[i];}// 保存结果int sum = 0;// 计算所有奇数长度子数组的和for (int start = 0; start < arrSize; start++){// 计算奇数长度子数组区间的和for (int length = 1; start + length <= arrSize; length += 2){// 计算奇数长度子数组的末尾索引int end = start + length - 1;// 根据前缀和数组计算奇数长度子数组的和sum += prefixSum[end] - prefixSum[start] + arr[start];}}// 返回结果return sum;
}
十一【提交结果】
-
Java语言版
-
Python语言版
-
C语言版