博文中会简要介绍Leetcode P0209题目分析及解题思路。

“Minimum Size Subarray Sum”是一道比较基础的滑动窗口问题。这道题要求我们得到最短窗口长度，并满足窗口内的和要大于等于给定的target。

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).

这道题的思路比较简洁明了。我们维护left和right两个指针，分别指向窗口的左边界和右边界，并且再维护一个sum变量用于存储窗口内各数的加和。下面简单讲解移动left和right的边界条件。

我们不断移动right指针，每次向sum累加当前right指针指向的元素。若sum大于等于给定的target，从sum中减去left指向的元素，并向后移动left，直到当前sum减去当前left指向的元素后小于target。此时left和right组成的窗口恰好满足窗口内的和大于等于target。接着重复上述操作，找到满足条件的最小窗口长度即可。

以下是Java的题解代码实现。

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int L = nums.length, minLen = L+1, left = 0, right = 0, sum = 0;
        while (right < L) {
            sum += nums[right];
            while (sum-nums[left] >= s) {
                sum -= nums[left];
                ++left;
            }
            
            if (sum >= s)
                minLen = Math.min(minLen, right-left+1);
            
            ++right;
        }
        
        return (minLen == L+1)? 0: minLen;
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int L = nums.size(), min_len = L+1, left = 0, right = 0, sum = 0;
        while (right < L) {
            sum += nums[right];
            while (sum-nums[left] >= s) {
                sum -= nums[left];
                ++left;
            }
            
            if (sum >= s)
                min_len = min(min_len, right-left+1);
            
            ++right;
        }
        
        return (min_len == L+1)? 0: min_len;
    }
};