所有奇数长度子数组Leetcode解决方案的总和


难度级别 易得奖学金
经常问 LinkedIn
排列

问题陈述

在这个问题中,给出了一个正整数数组。 我们必须计算并返回一个整数,即给定数组所有可能的奇数长度子数组的总和。 子数组是 排列.

使用案列

arr = [1,4,2,5,3]
58

说明:

arr的奇数长度子数组及其和为:
[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

arr = [1,2]
3

说明:

只有2个奇数长度的子数组[1]和[2]。 他们的总和是3。

接近(强力)

为了用蛮力解决这个问题,从这个问题很容易看出,我们只需要处理所有奇数长度的子数组并计算总和并返回就可以了。
我们可以通过以下简单的步骤来实现:

1.创建一个变量 总和 存储总和。
2.对所有从奇数开始的奇数长度子数组运行一个for循环 LEN= 1并继续将值增加2,同时 LEN <= n(数组的大小)。
3.在此循环中,运行 循环 对于从i = 0到i = n-len的子数组的起始位置。
4.在上面的循环中,为此索引从i开始并在i +结束的子数组运行一个循环LEN-1并添加此子数组的所有元素。
5.最后返回 总和.

所有奇数长度子数组Leetcode解决方案的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int len=1;len<=n;len+=2)
        for(int i=0;i<n-len+1;i++)
            for(int j=i;j<i+len;j++) 
                sum+=arr[j];
    
    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

Java程序

#include <bits/stdc++.h>
using namespace std;

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int len=1;len<=n;len+=2)
        for(int i=0;i<n-len+1;i++)
            for(int j=i;j<i+len;j++) 
                sum+=arr[j];
    
    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

所有奇数长度子数组Leetcode解的总和的复杂性分析

时间复杂度

O(n ^ 3): 我们使用了嵌套形式的三个循环,每个循环在以下时间运行:
第一个循环运行n / 2次。
第二个循环正在运行(n-LEN)次,在哪里 LEN 是1,3,4,…。
第三循环正在运行 LEN 倍。
总时间为(n / 2)*(n-LEN)*LEN。 因此,时间复杂度的上限为O(n ^ 3),其中n是给定数组的大小。

空间复杂度 

O(1): 空间复杂度是恒定的。

方法(时间优化)

如我们所见,上述蛮力解决方案具有O(n ^ 3)的时间复杂度。 我们可以将其最小化,因为在上述方法中,我们为不同的子数组多次添加了相同的元素。 如果以某种方式我们知道将某个特定元素添加或应添加到总和中的次数,则可以将时间复杂度从O(n ^ 3)降低到O(n)。

我们可以分析一下,如果我们取所有子数组(偶数和奇数长度),那么在这种情况下,索引i的特定元素将出现在所有子数组中,其起始索引小于i,结束索引大于i。 。

因此,可以说包含arr [i](0索引)的那些子数组的总数等于(i + 1)*(ni)。
将该值设为x。
其中有(x + 1)/ 2个奇数长度的子数组,其中包含arr [i]。
和x / 2个偶数长度的子数组,其中包含arr [i]。
因此,在我们的解决方案中,a [i]将贡献总和的(x + 1)/ 2倍。

我们可以通过一个简单的示例看到这一点:

令arr = [1、2、3、4、5]

所有奇数长度子数组Leetcode解决方案的总和

因此,奇数子阵列中每个元素arr [i]的贡献= arr [i] *((i + 1)*(ni)+1)/ 2。
可以使用单个循环完成此操作,因此该解决方案的时间复杂度将是线性的。

所有奇数长度子数组Leetcode解决方案的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int i=0;i<n;i++)
    {
        int contribution= ((i+1)*(n-i) +1)/2;
        sum+= contribution* arr[i];
    }

    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

Java程序

#include <bits/stdc++.h>
using namespace std;

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int i=0;i<n;i++)
    {
        int contribution= ((i+1)*(n-i) +1)/2;
        sum+= contribution* arr[i];
    }

    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

所有奇数长度子数组Leetcode解的总和的复杂性分析

时间复杂度

上) : 由于我们仅遍历数组的每个元素一次,因此时间复杂度将为O(n)。 其中n是给定数组的大小。

空间复杂度 

O(1): 我们没有使用任何额外的内存,因此空间复杂度将保持不变。