Easy

题目描述

给你一个正整数数组 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) 时间复杂度的算法吗？

解题思路

解题思路

这道题有两种主要解法：

方法一：暴力枚举（O(n³)）

最直接的思路是枚举所有可能的子数组，判断长度是否为奇数，如果是则计算其和并加入结果。具体步骤：

  1. 使用两重循环枚举所有子数组的起始和结束位置
  2. 判断子数组长度是否为奇数
  3. 如果是奇数长度，遍历该子数组计算和

方法二：数学优化（O(n)）- 推荐解法

关键观察：我们可以计算每个元素在所有奇数长度子数组中出现的次数。

对于位置 i 的元素 arr[i]：

  • 以该位置为中心或包含该位置的奇数长度子数组有多少个？
  • 左边有 i 个位置，右边有 n-1-i 个位置
  • 包含位置 i 的子数组起始位置可以是 [0, i]，结束位置可以是 [i, n-1]
  • 对于奇数长度的子数组，我们需要计算有多少种组合使得 (end - start + 1) 为奇数

通过数学分析，位置 i 的元素在所有奇数长度子数组中出现的次数为： ((i + 1) / 2) * ((n - i + 1) / 2) + ((i + 2) / 2) * ((n - i) / 2)

这个公式可以简化为一个更直观的形式。

代码实现

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int n = arr.size();
        int sum = 0;
        
        for (int i = 0; i < n; i++) {
            // 计算包含位置i的奇数长度子数组数量
            int left = i + 1;
            int right = n - i;
            int total = left * right;
            int odd = (total + 1) / 2;
            
            sum += arr[i] * odd;
        }
        
        return sum;
    }
};

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        total = 0
        
        for i in range(n):
            # 计算包含位置i的奇数长度子数组数量
            left = i + 1
            right = n - i
            total_subarrays = left * right
            odd_subarrays = (total_subarrays + 1) // 2
            
            total += arr[i] * odd_subarrays
        
        return total

public class Solution {
    public int SumOddLengthSubarrays(int[] arr) {
        int n = arr.Length;
        int sum = 0;
        
        for (int i = 0; i < n; i++) {
            // 计算包含位置i的奇数长度子数组数量
            int left = i + 1;
            int right = n - i;
            int total = left * right;
            int odd = (total + 1) / 2;
            
            sum += arr[i] * odd;
        }
        
        return sum;
    }
}

var sumOddLengthSubarrays = function(arr) {
    const n = arr.length;
    let sum = 0;
    
    for (let i = 0; i < n; i++) {
        // 计算包含位置i的奇数长度子数组数量
        const left = i + 1;
        const right = n - i;
        const total = left * right;
        const odd = Math.floor((total + 1) / 2);
        
        sum += arr[i] * odd;
    }
    
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
暴力枚举O(n³)O(1)
数学优化（推荐）O(n)O(1)

相关题目