6Companies30days

209. Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Solution

• Classic 2 pointers

class Solution {
public:
    
    Solution(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);        
    }

    
    
    int minSubArrayLen(int target, vector<int>& nums) {
        
        int l = 0, r = 0 ;
        int minSize = INT_MAX;
        
        int currSum = 0;
        
        while( r < nums.size() and l <= r ) {
                
            while( r < nums.size() and currSum < target ){
                currSum += nums[r];
                r++;
            }
        
            
            while( currSum >= target ){
                minSize = min(minSize, r-l);
                currSum -= nums[l];
                
                l++;   
            }
            
            
        }
        
        return minSize == INT_MAX ? 0 : minSize;
        
        
    }
};