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

Leetcode题目:前缀和

给你一个正整数数组 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) 时间复杂度的算法解决此问题

解题思路

前缀和

暴力做起来很麻烦。求数组连续子序列之和,那我们先试试前缀和。

首先是每个元素相加,这个没什么问题。问题在于如何处理前缀和。我们可以从样例一入手。从i=3开始,前缀和的规律是

  • result=sum[3]-0
  • result=sum[4]-sum[1]
  • result=sum[5]-sum[2]

当i=5时

  • result=sum[5]-0
  • result=sum[6]-sum[1] (如果有的话)
  • …

那写个双for完事了。至于进阶里提到的O(n)解决该问题,鉴定为纯纯的数学题,和前缀和没啥关系,所以就不看了。

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int size=arr.size();
        vector<int>sum;
        sum.resize(size+1);
        int result=0;
        for(int i=0;i<size;i++)
        {
            sum[i+1]=sum[i]+arr[i];
            result+=arr[i];
        }
        for(int i=3;i<=size;i+=2)
        {
            for(int j=i;j<=size;j++)
            {
                result+=sum[j]-sum[j-i];
            }
        }
        return result;
    }
};
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
在此留下你的评论x