leecode 209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

2、双指针法

注意到暴力破解法有许多地方涉及重复计算，因此我们自然得想到双指针方法，首先i，j指针都为0。然后移动i指针进行累加和，如果累加和大于s，则将当前的i-j+1的值记录下来，此即为当前的子数组具有的元素个数。然后移动j指针，如果在移动j指针的过程中，仍然能够满足i到j之间的元素和大于s，则更新当前的最小值，直到元素和不再大于s。然后继续重新移动i指针，循环往复直到数组结尾。过程中得到的所有最小子数组长度的最小者，即为最终的最小值。

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int minLen = Integer.MAX_VALUE;
        int thisSum = 0;
        for (int i = 0, j = 0; i < nums.length; i++) {
            thisSum += nums[i];
            while (thisSum >= s) {
                if (i - j + 1 < minLen) minLen = i - j + 1;
                thisSum -= nums[j];
                j++;
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

思路二：滑动窗口法

注意到题目限定的条件：该数组中的元素均是正整数。因此我们可以用滑动窗口法来解决，当和小于s时，滑动窗口右端点向右移动，使窗口增大；当和大于s时，滑动窗口左端点向右移动，使窗口缩小。

时间复杂度是O(n)，其中n为nums数组的长度。空间复杂度是O(1)。

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int left = 0;
        int right = -1;            //把[left, right]区间看作是一个滑动窗口，初始时滑动窗口中没有元素故right = -1
        int sum = 0;
        int len = nums.length + 1;        //n + 1比整个数组的长度还大，但要注意这个值其实是取不到的
        while (left < nums.length) {
            if (right + 1 < nums.length && sum < s) {        //当sum < s时，滑动窗口向右延伸使窗口内的值变大
                right++;
                sum += nums[right];
            } else {                                //当sum >= s时，滑动窗口left增大，使窗口向右缩进使得窗口内的值变小
                sum -= nums[left];
                left++;
            }
            if (sum >= s) {
                len = Math.min(len, right - left + 1);
            }
        }
        if (len == nums.length + 1) {
            return 0;
        } else {
            return len;
        }
    }
}