一、编程题：209. 长度最小的子数组（双指针-滑动窗口）

1.题目描述

??给定一个含有 n 个正整数的数组和一个正整数 target 。
??找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。 LeetCode题目链接。

2.示例1：

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

3.示例2：

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

4.示例3：

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

5.提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

6.提示：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

二、解题思路

这次还是老规矩练习一下双指针的思想，不枉练习这么多次双指针的题，现在双指针思路算是有一点长进了。其关键点还是该怎么去移动这两个指针？这一点要理清楚。；

1.思路

解决方法1（个人想法）：

Step 1.创建left，right分别指向滑动窗口的开始位置和结束位置，并用min存储数组中得到的最小长度和维护变量sum存储滑动窗口中的元素和（即nums[left]到nums[right]）;
Step 2.通过循环移动窗口的右指针right，当sum>=target时，记录当前滑动窗口长度，然后将left尝试向右边移动，直到sum<target为止，这样就能得到滑动窗口中最小长度;
Step 3.重复Step2步直到right>target遍历结束，就能得到子数组的最小长度了;

一开始就是用滑动窗口进行移动寻找子数组，但对循环的结束判定却把握不准，导致程序运行超时。

2.复杂度分析：

时间复杂度 O(N)?：其中N是数组的长度。指针left和right最多各移动N次。
空间复杂度 O(1)：使用常数额外空间。

3.算法图解

红色部分代表滑动窗口的大小。（注：本人不会做成流程动画，希望会的朋友可以私信我指点一二，说个软件名字也可以，谢谢）
请添加图片描述

三、代码实现

。每个代码块都写了注释，方便理解，代码还可以改进；
代码如下（示例）：
解法一：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        //方法一
        //初始状态下，left和right都指向下标0，sum的值为0。
        int left = 0, right = 0, length = nums.length-1, min = length+2, sum = 0;
        while(right <= length){
            sum += nums[right];
            //当滑动窗口内总数之和大于或等于目标值时，则left试着向右边移动，寻找最小长度
            while(sum >= target){
                min = Math.min(min, right-left+1);
                sum -= nums[left++];
            }
            right++;
        }
        return min == length+2 ? 0 : min;

        //错误思路
        <!-- if(sum < target){
            right++;
            if(right > length && min == length + 2) return 0;
        } 
        else{
            while(sum >= target){
                sum -= nums[left++];
            }
            min = Math.min(min, right-left+2);
            sum = 0; 
            
            left++;
            right = left;
        }
        return min == length+2 ? 0 : min; -->
    }
}

提交结果：

总结

以上就是今天要讲的内容，做题的时候，就是奔着双指针的思路进行解决的，练习这么多次现在逐渐找到了点感觉。我感觉就是双指针的关键点就是在于该怎么去移动两个指针，理清这一点之后离结果也就不远了，这次双指针都是指向滑动窗口来进行移动才能减少运行时间，但想好了怎么移动这两个指针，却卡着不知道该怎么结束循环，这块没想好导致程序运行最后一个例子时报运行超时。所以就赶紧记录一下这时刻。