所有奇数长度子数组的和（1588）

题目

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

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

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

示例

输入：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

算法

暴力法

外层循环是控制子序列长度，从1开始，最大为参数数组的长度

内层循环是当前子序列长度下截取的数组，数组的首位位置从[0,0+i)到[arr.length-1-i,arr.length-1)

function sumOddLengthSubarrays(arr) {
  let total = 0;
	for (let i = 1; i <= arr.length; i += 2) {
		for (let j = 0; j + i <= arr.length; j++) {
			total += arr.slice(j, j + i).reduce((acc, cur) => (acc += cur));
		}
	}
	return total;
}

数学规律法

在数组中选定一个i位置，包含这个数字arr[i]的子串总在左边共有i+1个选择（因为要求是连续子串，所以i之前有i个元素，加上左侧为空串，所以有i+1个），包含这个数字arr[i]的字串在右侧共有arr.length-i个选择（同理，右侧有arr.length-1-i个选择，加上右侧为空串，所以有arr.length-i个选择）

左侧为奇数长度的字串的个数有Math.floor(left/2)个 左侧为偶数长度的字串的个数有Math.floor((left+1)/2)个 右侧为奇数长度的字串的个数有Math.floor(right/2)个 右侧为偶数长度的字串的个数有Math.floor((right+1)/2)个

因为题目要求要奇数长度的字串，所以左侧长度+右侧长度===偶数，则有两种情况

• 左侧奇数长度 + 右侧奇数长度
• 左侧偶数长度 + 右侧偶数长度

所以，在选定一个i时，总共有左侧奇数长度字串数量 * 右侧奇数长度字串数量 + 左侧偶数长度字串数量 * 右侧偶数长度字串数量种符合题设的字串，此时用字串总数量（即 arr[i] 总共在求和过程中出现的次数） * arr[i]即能求出数字arr[i]在求和过程中总共的和

function sumOddLengthSubarrays(arr) {
	let sum = 0;
	for (let i = 0; i < arr.length; i++) {
		let left = i + 1,
			right = arr.length - i,
			left_odd = Math.floor(left / 2),
			left_even = Math.floor((left + 1) / 2),
			right_odd = Math.floor(right / 2),
			right_even = Math.floor((right + 1) / 2);
		sum += (left_odd * right_odd + left_even * right_even) * arr[i];
	}
	return sum;
}