27m｜1588. 所有奇数长度子数组的和

2021 年 8 月 29 日 链接：https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays/ 耗时：27m

题目

描述

给你一个正整数数组 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

  解答

  思路

• 当 length 等于 1 那么 result1 = arr[0]

• 当 length 等于 2 那么 result2 = result1 + arr[1]
• 当 length 等于 3 那么 result3 = result2 + arr[2] + (arr[0] + arr[1] + arr[2])
• 当 length 等于 4 那么 result4 = result3 + arr[3] + (arr[1] + arr[2] + arr[3])
• 当 length 等于 5 那么 result5 = result4 + arr[4] + (arr[2] + arr[3] + arr[4]) + (arr[0] + arr[1] + arr[2] + arr[3] + arr[4])
• 所以，设置 result 用于存放最终值
• 使用 i 遍历数组从 0 到 length
  • 在当前位置 i，使用 j 反向遍历数组，从 i 到 0
  • 遍历过程中将 j 的值进行叠加
  • 如果 i 与 j 之间的元素个数为奇数个，那么将值记录到 result 中

    代码

    /**
    * @param {number[]} arr
    * @return {number}
    */
    var sumOddLengthSubarrays = function(arr) {
    let result = 0
    let tempSum
    // 从 0 到 length 遍历 arr
    for (let i = 0; i < arr.length; i ++){
         // 清空 tempSum
       tempSum = 0
         // 从 i 到 0 反向遍历
       for(let j = i; j >= 0; j --){
           tempSum += arr[j]
             // 如果长度为奇数记录值
           if((i - j) % 2 === 0){
               result += tempSum
           }
       }
    }
    return result
    };