所有奇數長度子數組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是給定數組的大小。

也可以看看
島嶼外圍Leetcode解決方案

空間複雜度 

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): 我們沒有使用任何額外的內存,因此空間複雜度將保持不變。