嗨，大家好，我是袁厨（因为酷爱做饭，所以自己考取了厨师证）。之前一直看大家写的博客，学到了很多东西。然后最近萌生了自己写的想法，将自己知道的分享给需要的同学。以后每天会为大家分享leetcode精选题目的各种题解，并且每周会整理一下该周刷的所有题目，及解题框架。大家微信搜索【程序员爱做饭】关注我吧！
209，长度最小的子数组
- 题目描述
- 暴力解法
- 做题思路
- 题目代码
- 滑动窗口
- 做题思路
- 题目代码
- 总结
题目描述
暴力解法
做题思路
遇到这个题目的第一思路获取就是滑动窗口了，但是我们目前还没有学习滑动窗口，那我们可以先通过暴力解法解决呀，之前一个学长给我说，面试的时候不要管什么方法，你只要把题目做出来，就是好方法，所以我们先想着解决这个问题，然后再进行优化。我的大致思路就是，通过两层循环进行元素累加，第一个循环负责定位起点，然后从起点开始累加之后的元素，直到我们累加和大于等于目标值。然后保留当前子数组的长度，更换下一起点，直到遍历结束。
省略了绿指针移动过程
最后min的值为2，所以输出2.时间复杂度O(n^2),空间复杂度O(1)
题目代码
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int sum = 0;//定义累加的变量
int childlen = 0;//子数组长度
int minlen = Integer.MAX_VALUE;//int最大整数，常用
for(int i = 0 ;i < nums.length ; i++){
sum = 0;//每次都要归0，因为起点更换
for(int j = i;j < nums.length ;j++ ){
sum += nums[j];
//这里是大于等于，我原来理解错误题目，写的等于，浪费一次提交
if(sum >= s){
//子孩子长度
childlen = j-i+1;
//最小值
minlen = Math.min(minlen,childlen);
break;
}
}
}
//这里不可以直接返回minlen，因为有可能存在不存在子数组的情况。
return minlen==Integer.MAX_VALUE ? 0: minlen;
}
}
滑动窗口
做题思路
滑动窗口是数组操作中的一种重要方法，数组中很多题目都可以通过滑动窗口来解决。暴力法中，我们的红指针在一次循环中是不变的，绿指针进行移动，滑动窗口呢，就是通过不断调节子数组的起始位置和终止位置，进而得到我们想要的结果我们也可以看成是双指针的一种。
红指针和绿指针之间的距离就是滑动窗口的大小，符合条件的最小窗口大小为2，其实也很好理解这个思想，就是当红绿之间的和符合条件时，就移动红指针判断是否仍符合条件，不符合就移动绿指针，并记录最小的子长度，直到绿指针移动到最后。
时间复杂度O(n),空间复杂度O(1)
题目代码
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int chiledlen = Integer.MAX_VALUE;//子数组长度
int winlen = 0;//窗口大小
int sum = 0;
int i = 0;//起始长度位置
for(int j = 0 ; j < nums.length;j++){
sum += nums[j];
//发现符合条件的情况
while(sum>=s){
winlen = j-i+1;//窗口大小
chiledlen = Math.min(chiledlen,winlen);
//下面两行是滑动窗口的意义所在，改变起点位置，判断是否仍符合条件
sum-=nums[i];
i++;
}
}
return chiledlen == Integer.MAX_VALUE ? 0:chiledlen;
}
}
总结
这个题目是非常好的一个题，大家可以自己做一下，算是初探滑动窗口，大家有更好的方法可以评论讨论啊。
更多题目总结请扫描下面二维码，一块刷题呀。
作者：LeetCode
链接：https://leetcode-cn.com/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
