找到其總和大於給定整數的最小整數集合

-2

問題是 - 給出一個大小爲n和數字S的整數數組。您必須找到總和爲的最小集合的連續整數比S.如果沒有這樣的組存在的數量，輸入0找到其總和大於給定整數的最小整數集合

空間複雜度O（1）時間複雜-O（n）的

例 -

陣列A = {2時， 5,4,6,3,9,2,17,1}

S = 1 7

輸出= 2

Explanation-

可能的解決方案是： -

{2,5,4,6,3} = 2 + 5 + 4 + 6 + 3 = 20 （> 18）= 5號

{5,4,6,3,9} = 27（> 18）= 5號

{4,6,3,9} = 22（> 18） -4號碼

{6,3,9,2} = 20 = 4個數字

{3,9,2,17} = 4個數字

{9,2,17} = 3倍的數字

{2 ，17} = 2個數字

所以，最小= 2個數字。輸出= 2。

我的嘗試 - 我在O（n^2）時間複雜度中解決了這個問題。有沒有辦法通過迭代陣列來進一步優化它，並將複雜度降至O（n）？

不需要整個代碼。只要基本邏輯的基本思想就足夠了。謝謝。

來源

2016-11-05 Code_maniac

任何嘗試獨立解決這個問題？ – dasblinkenlight

我投票結束這個問題作爲題外話，因爲堆棧溢出不做你的功課。 – David

我用時間複雜度O（n^2）解決了它，但我無法進一步優化它。這個問題可以通過O（n）時間複雜度解決，而不需要使用額外的數組。 –

假設所有的整數都是非負和小號是肯定的，你可以使用下面的算法：

使用兩個指標，一個是當前序列開始的地方，另一個是它的結束位置。當該序列的總和太小時，可以通過遞增第二個索引來擴展序列;如果總和超過S，那麼您將記錄它是否是迄今爲止最好的，同時通過遞增第一個索引來從序列中刪除第一個值。

下面是在更正式的僞碼算法：

n = size(A) 
best = n + 1 
sum = 0 
i = 0 

for j = 0 to n - 1: 
    sum = sum + A[j] 
    while sum > S: 
     if j - i + 1 < best: 
      best = j - i + 1 
     sum = sum - A[i] 
     i = i + 1 

if best > n: 
    best = 0 

output best

空間複雜度是O（1）因爲有4個涉及（不計算輸入數組），其表示固定量數值變量的記憶。

時間複雜度是爲O（n）作爲倍，在內部循環的語句執行的總數是從不超過Ñ（我每次遞增，並且永遠不會繞過Ĵ）。

來源

2016-11-05 12:28:30 trincot

找到其總和大於給定整數的最小整數集合

回答

相關問題