假如到当前位置的前缀和为sumi，我们的目标是找到最大的j，满足sumi−sum（j−1）>=s。这样从j−i的区间和就是大于s的，找最大的j，是为了满足最短的要求。假如对于每一个位置i，我们都记录了符合条件的最大的j，就可以遍历找出最短的区间了。

以上算法的暴力实现，是O(n2)的。

优化： 由于ai>=0​，因此sumi是单调递增的，看到了单调性，我们自然而然的想起了二分，找最大的满足条件的j，我们可以通过二分来做，这样复杂度就从O(n2)变为了O(nlogn)。

我们可以继续优化这个算法。

我们设以as开始总和最初大于S时的连续子序列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)的复杂度就可以解决这个问题了。甚至可以不用预处理前缀