leetCode-1588. 所有奇数长度子数组的和-一一网

题目链接

题目描述

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

题解

思路一

暴力解决，遍历所有i开头并且长度为奇数的子数组，并计算他们的和进行累加，这里为了快速计算每个子数组的和，可以利用前缀和来进行减少计算。

前缀和的大概原理是这样的，利用一个数组prefixSumArray，这个数组里第i个元素是原来数组前i项的和（不包括第i个）。那么原数组i到j之间的和(包括i，j)为prefixSumArray[j + 1] – prefixSumArray[i]。代码如下

func sumOddLengthSubarrays(_ arr: [Int]) -> Int {
    var sum = 0
    let count = arr.count
    var prefixSumArray = Array(repeating: 0, count: count + 1)
    for i in 0..<count {
        prefixSumArray[i + 1] = prefixSumArray[i] + arr[i]
    }
    for i in 0..<count {
        sum += arr[i]
        if i + 2 < count {
            for j in stride(from: i + 2, to: count, by: 2) {
                sum += prefixSumArray[j + 1] - prefixSumArray[i]
            }
        }
    }
    return sum
}
复制代码

思路二

遍历数组中的所有元素，然后计算出这个元素会在多少个长度为奇数的子数组中出现过，然后进行累加就可以。然后这个问题就转化为了，数组中的某个元素会在多少个长度为奇数的子数组中出现过？
假设这个元素的位置为i，左边有l个元素，右边有r个元素。要想子数组的长度为奇数。可分为2种情况。

左右两边的元素个数都为偶数（0也算）
左右两边的元素个数都为奇数

通过排列组合可以得出，包含位置i,子数组长度为奇数的子数组的个数为，左边长度为偶数的个数*右边长度为偶数的个数 + 左边长度为奇数的个数 * 右边长度为奇数的个数。

对于长度l，偶数的个数为l / 2 + 1, 奇数的个数为（l + 1） / 2。最终代码如下

func sumOddLengthSubarrays(_ arr: [Int]) -> Int {
    var sum = 0
    let count = arr.count
    for i in 0..<count {
        let leftOdd = (i + 1) / 2
        let leftEven = i / 2 + 1
        let rightOdd = (count - i) / 2
        let rightEven = (count - 1 - i) / 2 + 1
        sum += arr[i] * (leftOdd * rightOdd + leftEven * rightEven)
    }
    return sum
}
复制代码