What is the easiest way to sum all odd-length subarrays?

Use the contribution counting formula to calculate how many odd-length subarrays each element appears in, then multiply by the element value and sum.

Can prefix sums improve performance for this problem?

Yes, prefix sums allow O(1) computation of any subarray sum, reducing nested summation in brute force approaches.

Does this problem work with negative numbers?

The original constraints specify positive integers, but the contribution and prefix sum approaches can extend to negatives without structural changes.

Why is counting contributions better than brute force?

Counting avoids iterating over all subarrays and leverages mathematical patterns, giving O(n) time instead of O(n^3).

How does this problem relate to the Array plus Math pattern?

It combines array traversal with combinatorial counting and prefix sum calculations, exemplifying the Array plus Math pattern.

#1588

Easy

auto_awesome数组·数学

LeetCode 题解工作台

所有奇数长度子数组的和

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。子数组定义为原数组中的一个连续子序列。请你返回 arr 中所有奇数长度子数组的和。示例 1：输入： arr = [1,4,2,5,3] 输出： 58 解释：所有奇数长度子数组和它们的和为： [1] = 1 [4] =…

数组数学前缀和

题目描述

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

进阶：

你可以设计一个 O(n) 时间复杂度的算法解决此问题吗？

lightbulb

解题思路

方法一：动态规划

我们定义两个长度为 $n$ 的数组 $f$ 和 $g$ ，其中 $f[i]$ 表示以 $\textit{arr}[i]$ 结尾的长度为奇数的子数组的和，而 $g[i]$ 表示以 $\textit{arr}[i]$ 结尾的长度为偶数的子数组的和。初始时 $f[0] = \textit{arr}[0]$ ，而 $g[0] = 0$ 。答案即为 $\sum_{i=0}^{n-1} f[i]$ 。

当 $i > 0$ 时，考虑 $f[i]$ 和 $g[i]$ 如何进行状态转移：

对于状态 $f[i]$ ，元素 $\textit{arr}[i]$ 可以与前面的 $g[i-1]$ 组成一个长度为奇数的子数组，一共可以组成的子数组个数为 $(i / 2) + 1$ 个，因此 $f[i] = g[i-1] + \textit{arr}[i] \times ((i / 2) + 1)$ 。

对于状态 $g[i]$ ，当 $i = 0$ 时，没有长度为偶数的子数组，因此 $g[0] = 0$ ；当 $i > 0$ 时，元素 $\textit{arr}[i]$ 可以与前面的 $f[i-1]$ 组成一个长度为偶数的子数组，一共可以组成的子数组个数为 $(i + 1) / 2$ 个，因此 $g[i] = f[i-1] + \textit{arr}[i] \times ((i + 1) / 2)$ 。

最终答案即为 $\sum_{i=0}^{n-1} f[i]$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\textit{arr}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        f = [0] * n
        g = [0] * n
        ans = f[0] = arr[0]
        for i in range(1, n):
            f[i] = g[i - 1] + arr[i] * (i // 2 + 1)
            g[i] = f[i - 1] + arr[i] * ((i + 1) // 2)
            ans += f[i]
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Checks if you can identify the relationship between element positions and odd-length subarrays.
question_mark
Wants a solution that avoids summing each subarray explicitly for larger arrays.
question_mark
Tests your ability to apply prefix sums or direct counting formulas in array problems.

warning

常见陷阱

外企场景

error
Forgetting that only odd-length subarrays count and summing even-length subarrays by mistake.
error
Attempting brute force without optimization, leading to unnecessary O(n^3) time.
error
Miscalculating the contribution count for each element in the formula approach.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute the sum of all even-length subarrays instead of odd-length ones.
arrow_right_alt
Find the average of all odd-length subarrays rather than the sum.
arrow_right_alt
Return a list of sums for each odd-length subarray instead of the total sum.

help

常见问题

外企场景

继续练习

#1524 和为奇数的子数组数目 #1685 有序数组中差绝对值之和 #1442 形成两个异或相等数组的三元组数目