209. Minimum Size Subarray Sum

https://leetcode.com/problems/minimum-size-subarray-sum/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.

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.

Thoughts

以l为头，r为底，如果当前sum没有到k，那么r继续往外拓展; 当满足时为了找出最短窗口，以r为底不断++l直到sum再次不满足。注意不是 == k. 如果是==k就用presum map。

Code

/*
 * @lc app=leetcode id=209 lang=cpp
 *
 * [209] Minimum Size Subarray Sum
 */
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int l = 0, r = 0, sum = 0, res = INT_MAX;
        while (r < nums.size()) {
            sum += nums[r];
            while (sum >= s) {
                res = min(res, r - l + 1);
                sum -= nums[l];
                ++l;
            }
            ++r;
        } 
        return res == INT_MAX ? 0 : res;
    }
};

Analysis

时间复杂度O(N).