209. Minimum Size Subarray Sum

Difficulty Level : Medium

Given an array of positive integers nums and a positive integer target, return the minimal length of a 
subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

 

Example 1:

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.
Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
 

Constraints:

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104
 

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

Solution

critical case : target=7, nums=1,2,3,100
we need to loop through the array(vector) and check if the temporary sum exceeds the target and then we have to move the starting point until the temporary sum does not exceed the target and then keep going.

#include <algorithm>

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int tmp_sum = 0;
        int min_len = INT32_MAX;
        int s = 0;
        for(int i=0; i<nums.size();i++){
            tmp_sum += nums[i];
            while(tmp_sum >= target)
            {
                min_len = min(min_len, i-s+1);
                tmp_sum -= nums[s];
                s++;
            }

            if(min_len == 1) return min_len;
        }
        if(min_len == INT32_MAX) return 0;
        return min_len;
    }
};