最短子列表包括N元素總> MIN

實施例：最短子列表包括N元素總> MIN

鑑於隨機數[1,5,1,1,3,10,5,4,2,1]，測試元件N=10 at index 5和MIN=20的列表。

最短的子列表包括10與total>20顯然列表[3,10,5,4]與total=22和size=4。

問題：

什麼是算法，以有效的方式找到這樣的子列表？

編輯：

有可能是滿足條件的「最短」不同的子列表。 [10,5,4,2]與[3,10,5,4]一樣短，也是有效的結果。
這個問題中的「子列表」是原始列表的一個連續的項目塊。 [5,10,5,4]不是一個有效的子列表（我會將它稱爲一個子集）。

來源

2011-03-04 Jens Struwe

你想如何處理關係？例如，[10,5,4,2]的長度相同，並且總和> 20. – 2011-03-04 15:04:43

Oha！我其實不想讓我的例子有聯繫：D。不過，我只需要知道列表的大小，而不是實際的內容。感謝您的評論。 – 2011-03-04 15:10:03

這個總和是否很小很重要嗎？與[10,5,5,4]的列表與您的和傑瑞的一樣短，但總和更高。 – 2011-03-04 15:19:15

以下算法應爲O（n）：

與測試元件開始去添加元素至左側，直至總和> =分鐘。這給出了子列表長度l（從索引i開始）的第一次猜測。沒有增加長度爲l的子列表的每個步驟（直到你到達你的測試元素）的開始索引i，並且每個步驟測試是否可以縮小子列表一（在右邊，即減小長度l）而不小於最小值。

照顧邊緣情況：總和不夠大或總和不夠大。

來源

2011-03-04 15:27:35 Howard

（他們爲什麼要刪除他們的答案？）我已經自己找到了你的方法。我發現它太複雜了，所以我開始了這個問題。 – 2011-03-04 15:39:29

尋找最短子列表> MAX是相同的查找最短子列表< = MAX其中總的子列表的超過MAX如果任一之前的項或後面加入：隨着[1,5,1,1,3,10,5,4,2,1]和MAX=20，[1,3,10]是包括一個子列表10但無效，因爲添加下一個5總共給出19 < MAX。第一個有效的子列表在這裏[5,1,1,3,10]。

算法：

對發現的最短的子表的長度創建。
創建光標left和right。
將兩個遊標都設置爲N。
將left移動到左邊while total(at left, ..., at N) <= MAX或left = 0。
1. 如果left > 0商店n - left + 1在。轉到6.
將right移動到右邊while total(at left, ..., at right) <= MAX或right = list.size - 1。
1. 如果right < list.size - 1店鋪right - left + 1在。
2. 其他：退貨list.size。
循環while left < N and right < list.size - 1：
1. 移動left一個向右。
2. 測試項目at right + 1，如果有的話。
  1. 如果total + at right + 1 > MAX商店right - left + 1在。
  2. 否則向右移動一個。

我給霍華德的答案，反正。

來源

2011-03-08 07:33:20

最短子列表包括N元素總> MIN

回答

相關問題