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).先从左往右累加数据，因此：
[2,3,1,2,4,3] 就变化成：[0,2,5,6,8,12,15]由于所有元素都是正数，所有[0,i]subarray都是也是正数，而且这样得到的vector就从无序的矩阵变成了递增序列。现在就好办了：对新得到的vector,从后往前遍历，例如：遇到15时，就用binary search查找15-7=8的位置，因此找upper_bound(8),然后计算此时的长度；当遇到12是，找upper_bound(12-7)…以此类推，最后的复杂度就是o(nlgn). 6. 想说一下这个题的思路，由于是正数，而且是求和，那么就通过子序列求和把无序的正数序列转成有序的序列。就可以用二分搜索了。这个思路是值得学习的，除了技巧性，尤其是可以打破思维里的看什么是什么的认知，上午讨论了，看到复杂的情况，就要想到背后有可能潜藏这简单的情况。比如这里，看到不规则的序列，但是有正数序列的限制，那么这个序列就可以转换成递增序列，或者说，这个无序的序列下潜藏或包裹这一个有序序列，就看自己能不能站在合适的角度去看了。所以，看问题不能只看到这个问题表面展现出来的样子，通常这个样子具有迷惑性、有时候很丑陋、很繁琐、很多corner case、很多if-else,这些并不是这个问题的样子。或者说，我们站的角度看到的这个问题不是问题的全貌，还一个角度则可能看到不一样的问题，所以，就要习惯站在不同角度看问题。上午谈的是，最容易的是站在相反的角度看问题，比如从左往右遍历如果很繁复，那么就从右往左看试一下。这都是最简单的这个思路的应用：站在不同位置看同一个问题！
//方法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不正确！ //如果整个过程遍历都没有大于给定的和，那么长度就该是0； //所以把len初始化INT_MAX,最后判断len是否还等于INT_MAX，如果等于，说明没有更新长度值，因此长度就是0。 }};//方法2：binary search:站在不同角度看问题，妙！class Solution {public: int minSubArrayLen(int s, vector<int>& nums) { // int n=nums.size(); vector<int> sums(n+1,0); //step 1:求所有子序列之和，其意义在于：站在不同角度看到序列的规则性！ 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; }};新闻热点
疑难解答
