假如到當前位置的前綴和為sumi，我們的目標是找到最大的j，滿足sumi?sum（j?1）>=s。這樣從j?i的區(qū)間和就是大于s的，找最大的j，是為了滿足最短的要求。假如對于每一個位置i，我們都記錄了符合條件的最大的j，就可以遍歷找出最短的區(qū)間了。

以上算法的暴力實現，是O(n2)的。

優(yōu)化： 由于ai>=0?，因此sumi是單調遞增的，看到了單調性，我們自然而然的想起了二分，找最大的滿足條件的j，我們可以通過二分來做，這樣復雜度就從O(n2)變?yōu)榱薕(nlogn)。

我們可以繼續(xù)優(yōu)化這個算法。

我們設以as開始總和最初大于S時的連續(xù)子序列as+...+at?1,這時as?1+...+at?2<as+...+at?2<S。

可以設計如下算法：

• 以s=t=sum=0開始
• 只要依然有sum<S，就不斷將at加入到sum中，并將t增加1
• 如果2中無法滿足sum>=S則終止，否則的話更新答案 res=min(res,t?s)
• 將sum減去as，s增加1然后回到2。

對于這個算法，因為t最多變化n次，因此只需要O(n)的復雜度就可以解決這個問題了。甚至可以不用預處理前綴