1588_javascript.js

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

// 2021.08.29 每日一题

/**
 * @param {number[]} arr
 * @return {number}
 */
// 1.
// 暴力 解法 时间复杂度 O(n3)
var sumOddLengthSubarrays = function (arr) {
  // 遍历奇数子数组的长度
  let res = 0;
  for (let i = 1; i <= arr.length; i += 2) {
    for (let j = 0; j <= arr.length - i; j++) {
      // length 为 此次遍历的长度
      let length = i;
      // 若 length = 3
      // res += arr[j+2]
      // res += arr[j+1]
      // res += arr[j+0]
      while (length--) {
        res += arr[j + length];
      }
    }
  }
  return res;
};

// 2.
// O(n) 时间复杂度 难度至少 medium
// 考虑每个元素i在排列组合种出现的次数