LeetCode Q209: 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.

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).

Solution: O(n) time O(1) space

	class Solution {
	public:
	int minSubArrayLen(int s, vector<int>& nums) {
	if(nums.size()==0)
	return 0;
	int l=0, r=0;
	int len=INT_MAX;
	int sum=nums[0];
	int sz=nums.size();
	while(r<(sz-1) || l<(sz-1)){
	if(sum<s){
	if(r<sz-1){
	r++;
	sum=sum+nums[r];
	}else
	return len<=nums.size()? len:0;
	}else{
	len=min(len, r-l+1);
	sum=sum-nums[l];
	l++;
	}
	}
	return len<=nums.size()? len:0;
	}
	};

view raw Q209MinimumSizeSubarraySum.cpp hosted with ❤ by GitHub

Rnd3 sol:

	class Solution {
	public:
	int minSubArrayLen(int s, vector<int>& nums) {
	int res=INT_MAX;
	if(nums.empty())
	return 0;
	int p0=0, p1=0;
	int sum = 0;
	for(; p1<=nums.size(); ){
	if(sum<s){
	sum+=p1<nums.size()?nums[p1]:0;
	p1++;
	}else{
	res = min(res, p1-p0);
	sum-=nums[p0];
	p0++;
	}
	}
	res=res==INT_MAX? 0:res;
	return res;
	}
	};

view raw Q209Rnd3.cpp hosted with ❤ by GitHub