Minimum Size Subarray Sum
Given an array of n positive integers and a positive integer s, find the minimal length of a 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.
Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.
Hide Tags
Array Two Pointers Binary Search
Hide Similar Problems
没想到合适的方法，参考别人的思路做出来的。
线性复杂度的方法是，先从头求和，直到和大于s才停下来，
然后平移，且移动起点以求缩小长度来满足和大于s，
直到移到最末尾，且不能再收缩为止，这期间的最小长度即是结果。
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int rst=0;
int sz=nums.size();
if(sz)
{
int idx1=0, idx2=0;
int sum=nums[0];
//keep adding untill sum >= s
while(idx2<sz && sum<s)
sum += nums[++idx2];
//if s is even bigger than all sum, return 0
if(idx2 == sz)
return 0;
//now we have a subset length to make sum >= s
rst = idx2+1;
//let's check for smaller length:
int len = rst;
while(idx2<sz)
{
//move idx2 --> right by 1 element, add next element to sum,
if(idx2<sz-1)
{
sum += nums[idx2+1];
len++;
}
idx2++;
//then keep moving idx1 one by one to check if (sum - nums[idx1]) > s
while((sum-nums[idx1])>=s)
{
sum -= nums[idx1++];
len--;
}
//untile smaller, and updating rst at the same time.
rst = (len<rst)?len:rst;
}
}
return rst;
}
};
4 ms.
关于 nlgn 的解法，也就是折半查找的方法，稍后再写。
