Shallow Web

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

August 29, 2021LeetCode

题目：1588. 所有奇数长度子数组的和

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。

子数组 定义为原数组中的一个连续子序列。

请你返回 arr 中 所有奇数长度子数组的和 。

刚开始使用回溯算法实现，后面才发现要求是连续子序列。

/**
 * @param {number[]} arr
 * @return {number}
 */
var sumOddLengthSubarrays = function (arr) {
  let len = 1
  const result = []
  while (len <= arr.length) {
    for (let i = 0; i <= arr.length - len; i++) {
      result.push(arr.slice(i, i + len).reduce((a, b) => a + b))
    }
    len += 2
  }
  return result.reduce((a, b) => a + b)
}

当然，这道题并没有那么简单，可以复用前面的计算来减少计算量，实现如下：

var sumOddLengthSubarrays = function (arr) {
  let result = 0
  for (let i = 0; i < arr.length; i++) {
    let prev = arr[i]
    let num = prev
    for (let j = 1 + i; j < arr.length - 1; j += 2) {
      prev = prev + arr[j] + (arr[j + 1] || 0)
      num += prev
    }
    result += num
  }
  return result
}
jianglin-wu

知命不惧，日日自新。