209.MinimumSizeSubarraySum.md

209. Minimum Size Subarray Sum

• 209. Minimum Size Subarray Sum [Array] [Two Pointers] [Binary Search] [Medium]

Tags

• [Array] [Two Pointers] [Binary Search] [Medium]

Problem

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:

Input: s = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: the subarray [4,3] has the minimal length under the problem constraint. 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

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        
        int sum = 0, minLen = INT_MAX;
        for (int i = 0, j = 0; i < nums.size(); i++) {
            sum += nums[i];
            
            while (sum >= s) {
                minLen = min(minLen, i - j + 1);
                sum -= nums[j++];
            }
        }
        
        return minLen == INT_MAX ? 0 : minLen;
    }
};

Time Complexity

• O(n)

Space Complexity

• O(1)

Notes

• Use Two Pointers, 20181113.

Related Problems

• 209. Minimum Size Subarray Sum [Array] [Two Pointers] [Binary Search] [Medium]