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

野生程序猿,专业铲屎官。#Github 账号