网站如何做浏览量,do_action wordpress 模板,专业网站建设微信网站定制,广告策划书模板文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【题目进阶】八【解题思路】九【时间频度】十【代码实现】十一【提交结果】 一【题目类别】
前缀和
二【题目难度】
简单
三【题目编号】
1588.所有奇数长度子数组的和 … 文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【题目进阶】八【解题思路】九【时间频度】十【代码实现】十一【提交结果】 一【题目类别】
前缀和
二【题目难度】
简单
三【题目编号】
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 1001 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 resC语言版
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语言版
