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。為什么？因?yàn)橐疫B續(xù)的subarray，用雙指針正好來(lái)表示這個(gè)連續(xù)的subarray的左右邊界。 2. 左右指針都初始化為l=0,r=0；然后右指針r右移知道[l,r]的和大于給定的和，條件先滿足，然后再找最小值，此時(shí)就可以移動(dòng)左指針l來(lái)壓縮長(zhǎng)度，如果移動(dòng)左指針發(fā)現(xiàn)和仍然大于給定的和，則繼續(xù)移動(dòng)左指針；如果移動(dòng)左指針發(fā)現(xiàn)此時(shí)的和小于給定的和，說(shuō)明不能在壓縮了，此時(shí)要移動(dòng)右指針來(lái)重新讓條件滿足。整個(gè)過(guò)程就是：右指針移動(dòng)為了滿足和大于給定的和，因此區(qū)間是expanded；左指針移動(dòng)則是為了壓縮這個(gè)subarray的size，讓得到最小值，因此區(qū)間是compressed. 3. 在debug過(guò)程中，發(fā)現(xiàn)自己仍然會(huì)漏掉一些邊界情況。第一，當(dāng)給的array是空的話，代碼需要加保護(hù)嗎？這一點(diǎn)還是給忽略了；第二，當(dāng)給的array的數(shù)都加起來(lái)還小于給定的和，結(jié)果正確嗎？ 4. 提示說(shuō)還可以用o(nlgn)的方法，那就是divide and conquer，分成兩半，分別左右求最小size，然后中間往兩邊擴(kuò)展也得到一個(gè)最小size，三個(gè)最小size取小者返回！ 5. 另外還有一個(gè)新的思路可以實(shí)現(xiàn)o(nlgn).先從左往右累加數(shù)據(jù)，因此：
[2,3,1,2,4,3] 就變化成：[0,2,5,6,8,12,15]由于所有元素都是正數(shù)，所有[0,i]subarray都是也是正數(shù)，而且這樣得到的vector就從無(wú)序的矩陣變成了遞增序列。現(xiàn)在就好辦了：對(duì)新得到的vector,從后往前遍歷，例如：遇到15時(shí)，就用binary search查找15-7=8的位置，因此找upper_bound(8),然后計(jì)算此時(shí)的長(zhǎng)度；當(dāng)遇到12是，找upper_bound(12-7)…以此類推，最后的復(fù)雜度就是o(nlgn). 6. 想說(shuō)一下這個(gè)題的思路，由于是正數(shù)，而且是求和，那么就通過(guò)子序列求和把無(wú)序的正數(shù)序列轉(zhuǎn)成有序的序列。就可以用二分搜索了。這個(gè)思路是值得學(xué)習(xí)的，除了技巧性，尤其是可以打破思維里的看什么是什么的認(rèn)知，上午討論了，看到復(fù)雜的情況，就要想到背后有可能潛藏這簡(jiǎn)單的情況。比如這里，看到不規(guī)則的序列，但是有正數(shù)序列的限制，那么這個(gè)序列就可以轉(zhuǎn)換成遞增序列，或者說(shuō)，這個(gè)無(wú)序的序列下潛藏或包裹這一個(gè)有序序列，就看自己能不能站在合適的角度去看了。所以，看問(wèn)題不能只看到這個(gè)問(wèn)題表面展現(xiàn)出來(lái)的樣子，通常這個(gè)樣子具有迷惑性、有時(shí)候很丑陋、很繁瑣、很多corner case、很多if-else,這些并不是這個(gè)問(wèn)題的樣子。或者說(shuō)，我們站的角度看到的這個(gè)問(wèn)題不是問(wèn)題的全貌，還一個(gè)角度則可能看到不一樣的問(wèn)題，所以，就要習(xí)慣站在不同角度看問(wèn)題。上午談的是，最容易的是站在相反的角度看問(wèn)題，比如從左往右遍歷如果很繁復(fù)，那么就從右往左看試一下。這都是最簡(jiǎn)單的這個(gè)思路的應(yīng)用：站在不同位置看同一個(gè)問(wèn)題！
//方法1：two pointerclass Solution {public: int minSubArrayLen(int s, vector<int>& nums) { // int l=0,r=-1,cur=0,n=nums.size(); if(n==0) return 0; int len=INT_MAX; while(r<n){ if(cur<s){ cur+=nums[++r]; }else{ len=min(r-l+1,len); cur-=nums[l++]; } } return len==INT_MAX?0:len;//bug:直接返回len不正確！ //如果整個(gè)過(guò)程遍歷都沒(méi)有大于給定的和，那么長(zhǎng)度就該是0； //所以把len初始化INT_MAX,最后判斷l(xiāng)en是否還等于INT_MAX，如果等于，說(shuō)明沒(méi)有更新長(zhǎng)度值，因此長(zhǎng)度就是0。 }};//方法2：binary search:站在不同角度看問(wèn)題，妙！class Solution {public: int minSubArrayLen(int s, vector<int>& nums) { // int n=nums.size(); vector<int> sums(n+1,0); //step 1:求所有子序列之和，其意義在于：站在不同角度看到序列的規(guī)則性！ for(int i=1;i<=n;i++){ sums[i]=sums[i-1]+nums[i]; } int len=INT_MAX; for(int i=n;i>0&&sums[i]>s;i--){ int j=lower_bound(sums.begin(),sums.end()+i,sums[i]-s)-sums.begin(); len=min(len,i-j); } return len==INT_MAX?0:len; }};新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
