LeetCode刷题16:滑动窗口解决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 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

解题思路：

? ? ? ? 有题意可知，我们需要返回的是总和符合目标值的长度最小的子数组，由于子数组只能是原数组的一个连续子区间，而连续区间就是滑动窗口的典型前提，因此就可以想到用滑动窗口算法解决。

? ? ? ? 首先我们可以循环检索每个元素依次，若有值与target相同的元素，即直接返回1，因为不会再有比1再小的数组长度。

图示(参考示例 1数据)：

? ? ? ? ?若没有长度为1的返回值那么咱们就开始进入正题：

? ? ? ? ? ? ? ? 设定两个指针：指针l(代表左指针)? ? ? ? 指针r(代表右指针)

? ? ? ? ? ? ? ? 当两指针之间的数之和小于target时? ? ? ? 指针r++????????

? ? ? ? ? ? ? ? 当和大于或等于target时? ? ? ? 与之前记录的比较，长度小，则保留? ? ? ? 指针l++

? ? ? ? ? ? ? ? 如此就能找出所有和等于target的可能并且可以计算出和为target的最小子数组长度

说着比较抽象，那就上图！(参考示例 1数据)：

第一、二步：

? ? ? ? res记录两指针之间的值，res值小于target，指针r右移

?第三、四步：

? ? ? ? res值大于target，与最小长度比较，小则替换，指针l右移

????????

第五、六步：?

? ? ? ? 若res值等于target，与最小长度比较，小则替换

后续步骤：

?

?代码实现：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        //设定指针l和指针r
        int l=0,r=1;
        //设定窗口最小长度，初始值要大于窗口最大长度
        int min=100001;
        //循环检索所有元素，等于target则返回1
        for(int x=0;x<nums.length;x++){
            if(nums[x]>=target) return 1;
        }
        if(nums.length==1) return 0;
        int res=nums[0]+nums[1];
        //开始窗口滑动操作
        while(r<nums.length){
            //小于target，指针r++
            if(res<target){
                r++;
                if(r>=nums.length) break;
                res+=nums[r];
            }
            //大于等于target，指针l++
            else if(res>=target){
                //记录最小长度
                min=Math.min(min,r-l+1);
                res-=nums[l];
                l++;
            }
        }
        //若min值没变，则说明没有符合条件的情况
        if(min!=100001) return min;
        return 0;
    }
}