LeetCode 1588. Sum of All Odd Length Subarrays

Given an array of positive integers arr, return the sum of all possible odd-length subarrays of arr.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: arr = [1,4,2,5,3]
Output: 58
Explanation: The odd-length subarrays of arr and their sums are:
[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
If we add all these together we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

Example 2:

Input: arr = [1,2]
Output: 3
Explanation: There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3.

Example 3:

Input: arr = [10,11,12]
Output: 66

Constraints:

• 1 <= arr.length <= 100
• 1 <= arr[i] <= 1000

Follow up:

Could you solve this problem in O(n) time complexity?

---

这题好难，呜。要求一个数组里所有奇数长度的subarray里所有element的sum。看了答案感觉也没有特别理解这个解法，感觉kind of像是硬背下来了这个公式，然后套公式就完事了，公式的推导过程有点难。

我现在的理解就是，我们考虑包含arr[i]这个数字的subarray。

首先考虑以它为subarray的start的，那么这个个数就是arr.length - i。比如长度为5的数组0 1 2 3 4，以第一个元素开始的subarray可以有5个，分别是长度为1 2 3 4 5，以第二个元素开始的subarray就是4个，长度分别是1 2 3 4。然后考虑以它为subarray的end的，个数是i + 1，比如以第一个元素结尾的subarray只有长度为1的它自己，以第二个元素结尾的就有两个。

然后下面这步我没有特别理解，视频里给的例子是从a->b->c，a->b有两个方法，b->c有三个方法，那么a->c就有2 * 3 = 6个方法。还没有很理解为什么这个例子能够迁移到这道题上。我就默认就是这样的吧，于是包含arr[i]的所有subarray的个数就是start * end。

再下一步理解了一会儿，那么我们知道subarray的个数了，这时候怎么知道有多少odd和多少even。其实理论上来说应该是一半一半，但是当长度为奇数的时候，odd应该会比even多一个，偶数的时候就是正好一半一半。怎么把这两种情况合并呢？可以采用(subarray + 1) / 2的方法，如果长度为奇数就正好是subarray一半多一个，如果长度为偶数这个+1不会有任何的副作用。于是我们就知道了有多少奇数长度的subarray了。

于是最后用arr[i] * subarray个数，遍历一遍整个数组，最后就是题目要求的结果了。

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int result = 0;
        for (int i = 0; i < arr.length; i++) {
            int end = i + 1;
            int start = arr.length - i;
            int timeInSubarray = start * end;
            int oddTime = (timeInSubarray + 1) / 2;
            result += (oddTime * arr[i]);
        }
        return result;
    }
}

reference：

LeetCode - The World's Leading Online Programming Learning Platform

https://youtu.be/J5IIH35EBVE