Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length under the PRoblem constraint.

click to show more practice.

More practice: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

s思路： 1. two pointer。為什么？因為要找連續的subarray，用雙指針正好來表示這個連續的subarray的左右邊界。 2. 左右指針都初始化為l=0,r=0；然后右指針r右移知道[l,r]的和大于給定的和，條件先滿足，然后再找最小值，此時就可以移動左指針l來壓縮長度，如果移動左指針發現和仍然大于給定的和，則繼續移動左指針；如果移動左指針發現此時的和小于給定的和，說明不能在壓縮了，此時要移動右指針來重新讓條件滿足。整個過程就是：右指針移動為了滿足和大于給定的和，因此區間是expanded；左指針移動則是為了壓縮這個subarray的size，讓得到最小值，因此區間是compressed. 3. 在debug過程中，發現自己仍然會漏掉一些邊界情況。第一，當給的array是空的話，代碼需要加保護嗎？這一點還是給忽略了；第二，當給的array的數都加起來還小于給定的和，結果正確嗎？ 4. 提示說還可以用o(nlgn)的方法，那就是divide and conquer，分成兩半，分別左右求最小size，然后中間往兩邊擴展也得到一個最小size，三個最小size取小者返回！ 5. 另外還有一個新的思路可以實現o(nlgn).先從左往右累加數據，因此：

由于所有元素都是正數，所有[0,i]subarray都是也是正數，而且這樣得到的vector就從無序的矩陣變成了遞增序列?，F在就好辦了：對新得到的vector,從后往前遍歷，例如：遇到15時，就用binary search查找15-7=8的位置，因此找upper_bound(8),然后計算此時的長度；當遇到12是，找upper_bound(12-7)…以此類推，最后的復雜度就是o(nlgn). 6. 想說一下這個題的思路，由于是正數，而且是求和，那么就通過子序列求和把無序的正數序列轉成有序的序列。就可以用二分搜索了。這個思路是值得學習的，除了技巧性，尤其是可以打破思維里的看什么是什么的認知，上午討論了，看到復雜的情況，就要想到背后有可能潛藏這簡單的情況。比如這里，看到不規則的序列，但是有正數序列的限制，那么這個序列就可以轉換成遞增序列，或者說，這個無序的序列下潛藏或包裹這一個有序序列，就看自己能不能站在合適的角度去看了。所以，看問題不能只看到這個問題表面展現出來的樣子，通常這個樣子具有迷惑性、有時候很丑陋、很繁瑣、很多corner case、很多if-else,這些并不是這個問題的樣子。或者說，我們站的角度看到的這個問題不是問題的全貌，還一個角度則可能看到不一樣的問題，所以，就要習慣站在不同角度看問題。上午談的是，最容易的是站在相反的角度看問題，比如從左往右遍歷如果很繁復，那么就從右往左看試一下。這都是最簡單的這個思路的應用：站在不同位置看同一個問題！