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

(Updated: )
LeetCode

Q

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

A

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int len = arr.length, res = 0;
        for(int i = 0; i < len; i ++){
            int LeftOdd = (i+1)/2, LeftEven = i/2+1;
            int RightOdd = (len-i)/2, RightEven = (len-1-i)/2+1;
            res += arr[i]*(LeftOdd*RightOdd + LeftEven*RightEven);
        }
        return res;
    }
}

  • 思路
    没必要计算所有满足条件的数组，只需要知道每个元素会出现的次数，然后乘以其值，求和就可以得到结果
    • odd奇数，even偶数
    • 对于每个元素i(数组中下标为i)来说，要构成奇数长度的子数组
      即 i左边的元素个数left+i本身自己一个+右边元素的个数right=奇数
      即 left+right=偶数
    • 满足a+b=偶数就只有两种情况
      1. 奇数+奇数=偶数
      2. 偶数+偶数=偶数
      1. 所以只需要求得i左边可以选择奇数长度的可能有多少种，即left_odd,同样求右边奇数right_odd
        就可以求出策略1有多少种可能
      2. 所以只需要求得i左边可以选择偶数长度的可能有多少种，即left_odd,同样求右边偶数right_odd
        就可以求出策略1有多少种可能，注意0也算选择的一种可能
    • 即元素i在所有奇数长度子数组出现的次数总和是
      left_oddright_odd+left_evenright_even
    • 元素i左边元素共有i个，右边元素共有siz-i-1个

要算长度为奇数的子序列的总的数组和，则需要知道每个数字在各个长度为奇数的子数组中出现的次数，比如说1，4，2，5，3这个序列，长度为3的子序列（1，4，2）（4，2，5）（2，5，3）中，4出现了2次，2出现了3次等，所以问题的关键就变成了如何找每个数字在各个子序列中出现的次数。
对于数组中的一个数字来说，它前面的数字可以出现 0 ~ i-1 次，它后面的数字可以出现 0 ~ n-i 次。要是前面的数字出现偶数次，则i后面的数字也应该出现偶数次，前面奇数次，后面同样奇数次。

  • 时间复杂度
    O(N)

  • 空间复杂度
    O(1)