Leetcode: Minimum Size Subarray Sum (4ms) analysis and solution

PROLBEM:

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.

Analysis:

Using moving window to sweep from left to right, O(n):

1. initial window set as: left=0, right =0;  sum=0;
2. when sum < target, increase the right until the sum is >=target;
3. when sum >=target, update the minimal length if needed;
    remove the first component in sum;
    increase the left by one until sum<target;

NOTE some trivial marked as red in codes.

/////////////////////////////////////////////////////////////////////////
//code 4ms

class Solution {

public:

       int minSubArrayLen(int s, vector<int>& nums) {

              int l = 0, r = 0, n = nums.size(), sum = 0, len = -1;

              if (n == 0)return 0;

              while (r <= n){

                     //increase right   

                     if (sum<s){

                           if (r == n)break;

                           sum += nums[r];

                           ++r;

                     }

                     //increase left

                     else if (sum >= s){

                           int lenTmp = r - l;

                           if (len == -1)len = lenTmp;

                           else if (lenTmp<len)len = lenTmp;

                           else;

                           if (len == 1)return 1;

                           sum -= nums[l];

                           l++;

                     }

              }

              return len == -1 ? 0 : len;

       }

};