【LeetCode每日一题】——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 <= 100
• 1 <= arr[i] <= 1000

七【题目进阶】

• 你可以设计一个 $O(n)$ 时间复杂度的算法解决此问题吗？

八【解题思路】

• 该题很容易想到的思路就是暴力模拟，这个方式确实很简单，不过复杂度太高
• 所以使用前缀和方法来解决该问题可以降低时间复杂度
  • 计算前缀和数组，前缀和数组的每一位表示从原数组的开始到每一位的累加和
  • 然后使用简单的数学运算找到所有奇数长度子数组
  • 最后使用前缀和数组对找到的所有奇数长度子数组求和
• 最后返回结果即可
• 具体细节可以参考下面的代码

九【时间频度】

• 时间复杂度：$O(n^2)$，$n$为传入的数组的长度
• 空间复杂度：$O(n)$，$n$为传入的数组的长度

十【代码实现】

1. 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;}
}

2. 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

3. 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;
}

十一【提交结果】

1. Java语言版
   

2. Python语言版
   

3. C语言版