滑动窗口处理问题
关联Leetcode:209 长度最小的字串
滑动窗口可以用来降低时间复杂度，本质是一个双指针
复杂度:O(N)
可以这样去理解:
- 由于窗口的头部一定会从首位开始，因此我们无需过多考虑头部
- 用for循环计算窗口的尾部
- 每次计算，都是计算窗口头部到窗口尾部所在的数组的值
- 当满足条件，则可以将头指针向后推动一下，同时删除头指针对应的值(因为窗口左侧已经向后一位，此时对应位置的值也需要被处理)
- 部分情况下，需要继续判断窗口内值的和(因为有的时候，你可能滑动右指针的时候，加入了一个较大的值，因此需要考虑，添加这个值后，这个窗口还需要这么大么)
听着有点空旷，具体看code吧
大致题思路
- 生成:最大窗口长度、左指针值(得手动创建因为只有一层for)、当前窗口内元素的和、当前窗口的长度
- 写一层for循环，让右指针不断的向后移动
- for循环内部:依次将当前窗口内元素的和当前尾指针对应的值(计算当前窗口的长度)
- for循环内部:如果发现当前窗口内元素的和>=target 则说明我们这个窗口内的和已经大于等于target了，此时进入一个while循环，while循环条件为**当前窗口的和大于target
- while内部:先记录当前窗口的长度，并和最小窗口长度对比，如果更小则覆盖，然后将头指针向右移动一位(让窗口内最左边的元素离开窗口)，并且将窗口长度-1(因为窗口最左边的元素已经没了，长度自然-1)
- while内部:完成5操作后，如果发现窗口的内的和还是大于target，则说明还可以继续减小窗口长度，继续跑第5步。
- 当for循环遍历完了(即为窗口尾指针已经到达最后了)，则弹出循环，并返回最小的长度
- (注意)如果窗口已经蔓延到整个数组内了，还是比不过target，则你需要返回为0，简单的搞就是看下最大窗口长度是否和初始化的值一样，一样就说明出现这个问题，返回0即可
// 题解
// 目标:给一个targe，从头开始计算所有的元素，查看多少个**连续的元素之和**等于target
// 标准思路:两个for循环，外层i表示连续元素的头部，内层j表示需要被添加的最后一个对象的元素，外层i+内层j中间框起来的空间之和大于等于target，则说明这个部分是正确的，此时将i向后面移动一位。继续计算
// 滑动窗口:一个for，外层i代表连续元素的尾部，然后给一个下标变量，从0开始，统计该下下标到外层这个区域的和，看是否大于target，大于则记录下中间有几个元素，然后将下标计数器+1，继续计算
func min(x,y int)int{
if x<=y{
return x
}
return y
}
func findNum(target int,nums []int)int{
// 创建最大值
maxResult:=10000000
// 创建下标记录器(记录窗口左侧)
low:=0
// 创建当前记录值(当前滑动窗口的总和)
nowNum:=0
// 当前窗口长度(当前滑动窗口的长度)
nowWindowsLen:=0
// 创建外层for循环
for i:=0;i<len(nums);i++{
// 求出本轮循环后，窗口内值的大小，将下标记录器+1
nowNum=nowNum+nums[i]
nowWindowsLen++
// 检查到值大于target，则记录下当前长度，然后和最大值比较，如果小于最大值，则覆盖最大值
// 然后将窗口左边(low)向右边推一格，继续检查是否大于target(因为你要考虑刚添加出来得到i下标的大小是否很大，例如target=11 窗口[1,2,3,4,11111],这种情况下，滑动窗口最多可以滑动到[4]这一个元素上这种情况)
for (nowNum>=target){
maxResult=min(maxResult,nowWindowsLen)
nowNum=nowNum-nums[low]
low++
nowWindowsLen--
}
// 检查到如果值没有大于target，则继续循环
}
// 判断:如果所有值相加，都没法等于target，就需要弹出了
if maxResult==10000000{
return 0
}
return maxResult
}
func minSubArrayLen(target int, nums []int) int {
return findNum(target,nums)
}