My easy to understand c++ solution,4ms,constant space


  • 0
    L

    mainly two steps :
    1,calculate the first k elements sum,after calculation,nums[0]=0, and nums[i]stores the sum of origin nums 0-(i-1).
    2,use two pointer p1 and p2, if nums[p2]-nums[p1]>=s,then compare p2-p1 with the min val we mantain,if p2-p1<min then update min=p2-p1;
    3,after finished,if min = MAX,means not satisfy,return 0; otherwise just return the min value;

    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            int len=nums.size();
            if(len<1)   return 0;
            int tmp1=nums[0],tmp2;
            nums[0]=0;
            for(int i=1;i<len;i++)
            {
                tmp2=nums[i];
                nums[i]=tmp1+nums[i-1];
                tmp1=tmp2;
            }
    		nums.push_back(tmp1+nums[len-1]);
    		len++;
    		int p1=0,p2=1,min=999999;//min init to MAX
    		while(p2<len)
    		{
    			while(p1<p2)
    			{
    				if(nums[p2]-nums[p1]>=s)//p2-p1 is a candidate result
    				{
    					if(p2-p1<min)
    						min=p2-p1;
    					p1++;// move p1 forward
    				}
    				else
    				{
    					break;// just jump out and move p2 forward
    				}
    			}
    			p2++;
    		}
    		if(min==999999)//if min == MAX,return 0
    			min=0;
    		return min;
        }
    };

  • 0
    M

    after p1++, insert
    if(p1==p2) return min; // to avoid checking of some extra cases


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.