总览

• 什么是窗口
• 什么是滑动窗口
• 滑动窗口用来解决什么问题
• 从长度最小的子数组入门

什么是窗口

在数组或字符串(本质是字符数组)中，定义一个左边界l，一个右边界r，左右边界之间的内容[l，r](也可以不包含左右边界的内容)，我们称之为窗口

什么是滑动窗口

窗口的左右边界都朝一个方向进行移动，一般情况都是向右进行移动

移动左边界时，l++，窗口内容减少

移动右边界时，r++，窗口内容增加

通过一定条件移动左右边界，就可以不断改变窗口内容，这就是滑动窗口

滑动窗口用来解决什么问题

数组中的窗口，本质就是子数组

字符串中的窗口，本质就是子串

所以滑动窗口一般用来解决数组子数组或字符串子串的问题

从长度最小的子数组入门

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [nums(l), nums(l+1), ..., nums(r-1), nums(r)]，并返回其长度 。 如果不存在符合条件的子数组，返回 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 <= 10(9)
• 1 <= nums.length <= 10(5)
• 1 <= nums[i] <= 10(5)

分析

题目给出的核心信息：nums是正整数的数组，也就是说数组内的每一个元素都是正整数，即nums[i] >= 1

我们可以推断出以下结论：

• 子数组以nums[i]开头时，子数组长度每+1，子数组和增加

拿示例1来分析，target = 7，nums = [2，3，1，2，4，3]

当i = 0时，以nums[0]开头的子数组分别为：

1. [2] - 子数组和为2 < target7，不满足条件

2. [2，3] - 子数组和为5 < target7，不满足条件

3. [2，3，1] - 子数组和为6 < target7，不满足条件

4. [2，3，1，2] - 子数组和为8 >= target7，满足条件，此时子数组长度为4

5. [2，3，1，2，4] - 子数组和为12 >= target7，满足条件，此时子数组长度为5

6. [2，3，1，2，4，3] - 子数组和为15 >= target7，满足条件，此时子数组长度为6

优化点：当查找到第4步时，第5步和第6步就没必要查找了

为什么可以这么优化？

数组元素nums[i] >= 1，满足条件的子数组 + 一个正整数时，一定也是满足条件的子数组，但是此时子数组长度+1，也就不会是长度最小的子数组 

所以以nums[0]开头，满足条件的最小子数组长度为4

同理可以求出其他元素开头，满足条件的子数组：

• i = 1，满足条件长度最小子数组为：[3，1，2，4] ，长度为4
• i = 2，满足条件长度最小子数组为：[1，2，4] ，长度为3
• i = 3，满足条件长度最小子数组为：[2，4，3] ，长度为3
• i = 4，满足条件长度最小子数组为：[4，3] ，长度为2
• i = 5，没有满足条件的子数组

方法一：暴力法

依据上面的分析，一种可行的方法是，我们依次求出以每一个元素开头，满足条件长度最小的子数组，然后取最小值即可

代码：

func minSubArrayLen1(target int, nums []int) int {
    var result int
    numsLen := len(nums)
    // 特殊判断
    if numsLen == 0 {
        return result
    }

    for l, _ := range nums {
        // 统计以l开头的和
        sum := 0
        for r := l; r < numsLen; r++ {
            sum += nums[r]
            // 满足条件
            if sum >= target {
                // 计算当前满足条件的子数组长度
                temp := r - l + 1
                // 是第一个满足条件的值或者比已有结果更短时，纪录最优的结果
                if result == 0 || temp < result {
                    result = temp
                    break
                }
            }
        }
    }
    return result
}

• 时间复杂度：两层循环，时间复杂度为O(n^2)
• 空间复杂度：常数空间，空间复杂度为O(1)

哪里可以优化

还是拿示例1来分析，target = 7，nums = [2，3，1，2，4，3]

	左边界l = 0	左边界l = 1	左边界l = 2	左边界l = 3	左边界l = 4	左边界l = 5
右边界r = 0	[2]❌
右边界r = 1	[2，3] ❌	[3]❌
右边界r = 2	[2，3，1] ❌	[3，1]❌	[1]❌
右边界r = 3	[2，3，1，2] ✅	[3，1，2]❌	[1，2]❌	[2]❌
右边界r = 4		[3，1，2，4]✅	[1，2，4]✅	[2，4]❌	[4]❌
右边界r = 5				[2，4，3]✅	[4，3]✅	[3]❌

有个规律：当左边界l++时，满足条件子数组的右边界不变或变大，右边界不会减小

为什么右边界不会减小？

因为当右边界减小时，子数组(窗口)会回退到上一个不满足条件的子数组，比如

• 左边界l = 0，[2，3，1，2]右边界减小，回退到[2，3，1]

因为回退的子数组本来就不满足条件，此时左边界++，窗口内容减少，更加不可能满足条件，所以这部分是无效计算，可以优化掉

对方法一进行优化：

• 当l = 0时，记录满足条件的子数组右边界为r
• 当l > 0时，直接从[l，r]开始查找符合条件的子数组，因为当l++时，右边界不可能减小，所以[l，r - 1]子数组不需要做无效计算 

方法二：滑动窗口

步骤：

1. 定义左边界l = 0，右边界r = 0，子数组(窗口)和sum = 0
2. 循环移动右边界r++，记录子数组和sum += nums[r]
3. 当sum >= target时，记录最优结果
4. 此时继续移动右边界时，子数组肯定都满足条件，但子数组长度+1，不是最优结果，属于无效计算。开始尝试查找nums[l+1]开头的长度最小子数组，sum -= nums[l]，移动左边界l++
5. 当sum >= target还满足时，继续步骤4
6. 当sum < target时，继续步骤2
7. 当右边界r越界时，退出，返回最优的结果

代码：

func minSubArrayLen2(target int, nums []int) int {
   var result int
   numsLen := len(nums)
   // 特殊判断
   if numsLen == 0 {
      return result
   }

   // 纪录滑动窗口内的值
   var sum int
   // 左边界
   var l int
   for r, num := range nums {
      // 右边界++，滑动窗口内的值+sum
      sum += num
      // 满足条件时，循环判断
      for sum >= target {
         // 计算当前滑动窗口的长度
         temp := r - l + 1
         // 第一个满足条件的滑动窗口或比已有结果更短时，纪录最优的结果
         if result == 0 || temp < result {
            result = temp
         }

         // 滑动窗口内的值-num[l]
         sum -= nums[l]
         // 左边界++
         l++
      }
   }
   return result
}

• 时间复杂度：遍历数组一次，时间复杂度为O(n)
• 空间复杂度：常数空间，空间复杂度为O(1)