尺寸最小的子陣列的具有比給定值總和

Question

原來的問題是

具有比給定整數數組和一個數x的給定值 總和

最小的子陣列中，找到與總和最小的子陣列比給定的值。在http://www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/

但如果問題只是找到最小的子陣列的大小，我們可以使用分而治之的方法嗎？

算法： Size_of_min_subarray（1，N）=的

分鐘{Size_of_min_subarray（1，N/2），Size_of_min_subarray（N/2，N），Size_of_array_containing mid_element（S）}

Size_of_array_containing_mid_element計算公式如下：

取中間元素，初始化sum = mid元素/中間元素和num_elements = 1/2的總和，基於n爲奇數或偶數.if總和< =給定值，檢查數字其右側或左側更大。將該更大的元素添加到總和並增加num_elements 。重複，直到sum>給定值。

插圖：

1,4,45,6,0,19和閾值= 51

MIN_SIZE =分鐘{MIN_SIZE {1,4,45}，{MIN_SIZE} 6,0,19 ，min_containing_45and6}

min_containing_45and6：

總和=中間元件/中間元件的總和= 45 + 6 = 51 < = 51，num_elements = 2。由於4> 0加4求和，sum = 55並增加num_elements。 num_elements = 3。

min_size = min {not possible，not possible，3} = 3。

這算法是否正確？我認爲它的複雜性如果O（logn），是嗎？

編輯：我意識到，我用來找到Size_of_array_containin_mid_elemnts的算法是錯的。任何人都可以提出一個算法來找到這個值？

Answer 1

1. 沒有亞線性算法可以解決這個問題，因爲它必須考慮每個數組元素至少一次（最壞的情況）。

2. 你的算法缺少「base」步驟，即Size_of_min_subarray(1,n)小n（無論「小」是什麼）。

3. 的復發你的算法是F(n)=2*F(n/2)+G(n)其中​​是的Size_of_min_subarray複雜性大小n和G(n)是的Size_of_array_containing_mid_element(n)複雜性。由於G(n)~O(n)，您的算法是O(n)。

Answer 2

1. 如果你只是試圖找到最小的子陣列（如果我讀這正確），不含任何其他參數，是不是永遠是不管大小1陣列？

2. 我會這樣做（可能更快的方式）的方式是將2個「指針」指向原始數組中的索引。您在循環中移動數組中的一個「指針」，直到從後「指針」到前「指針」的值的總和大於值x。您可以很容易地存儲該子數組或根據您想要對該信息執行何種操作而保存該長度。一旦找到可行的解決方案，就可以將後面的「指針」向前移動，直到兩個「指針」之間的和小於閾值。一旦發生這種情況，您再次向前移動前面的「指針」並重覆上述步驟。您比較子陣列的長度，並最終提出正確的答案。運行時間是O（n^2），但它得到正確的答案。

你可以看到的唯一問題就是它可能會遺漏一些情況。例如，如果你有{45,1,0,4,6,19}（閾值仍然是51），我認爲通過分割數組/列表的方式你可能會錯過一個解決方案，和6個在不同的列表中。

請糾正我，如果我錯了，但我認爲我有什麼是接近。

Answer 3

一個非常簡單的算法是獲得每個可能的子數組大小的最大值，直到你有一個總數大於給定值的子數組。

所以，如果你有一個6個元素的數組，你開始檢查是否有一個大於1的子數組大於或等於那麼給定的值（換句話說，大於給定值的單個值）。如果沒有檢查大小爲2的子數組。如果不檢查大小爲3的子數組，並且它繼續...

最糟糕的情況是您需要總和所有數組值以達到給定值。