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

分析

1.暴力解法

暴力解法肯定是最直观的方法，通过两层for循环，不断的寻找子序列，那么时间复杂度就很明显是O(n²)。

2.滑动窗口

定义两个指针，利用滑动窗口，不断的调节子序列的起始位置和终止位置，从而得到想要的结果。
如果使用滑动窗口，需要确定以下三点：

• 窗口内是什么？
• 如何移动窗口的开始位置？
• 如何移动窗口的结束位置？

窗口内是什么：窗口内应满足其和>=target且是长度最小的连续子序列。
开始位置如何移动：如果窗口内值的和>=target，那么他就应该向前移动(缩小子序列)。
结束位置如何移动：如果窗口内值的和<=target，那么他就应该向前移动(扩大子序列)。

实现

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        //定义开始指针
        int l = 0;
        //存储子序列值的和
        int sum = 0;
        //子序列长度
        int ans = Integer.MAX_VALUE;
        for(int r = 0;r<nums.length;r++){
            //子序列求和
            sum += nums[r];
            //当子序列的和大于target时 缩小子序列
            while(sum>=target){
                //计算最小子序列
                ans = Math.min(ans,r-l+1);
                //缩小子序列
                sum -= nums[l++];
            }
        }
        return ans == Integer.MAX_VALUE?0:ans;
    }
}