Minimum Size Subarray Sum

LeetCode #209

Description:

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Example:

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.

Idea:

Solution:

Suppose we know the prefixSum of each index i.

At any index i, we check if it is >= target. If so, we decrease its range from the left side, and check if it still satisfy the condition.

Code:

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        if(nums.size()==0)
            return 0;

        int sum=0;
        int min_len=INT_MAX;
        int j=0;
        for(int i=0; i<nums.size(); ++i){
            sum += nums[i];
            while(sum>=s){
                min_len = min(min_len, i-j+1);
                sum -= nums[j];
                j++;
            }
        }

        return min_len==INT_MAX? 0: min_len;

    }
};