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