209.长度最小的子数组(滑动窗口类）

209.长度最小的子数组

209.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

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

提示：

• $1<=target<=10^9$
• $1<=nums.length<=10^5$
• $1<=nums[i]<=10^5$

思路一：暴力解法
这道题目暴力解法当然是 两个for循环，然后不断的寻找符合条件的子序列，时间复杂度很明显是$O(n^2)$。

Go代码如下：

func minSubArrayLen(s int, nums []int) int {n := len(nums)if n == 0 {return 0}ans := math.MaxInt32for i := 0; i < n; i++ {sum := 0// 以每个i分别作为各个窗口的起点，找符合条件时的窗口终点jfor j := i; j < n; j++ { sum += nums[j]if sum >= s {ans = min(ans, j - i + 1)break}}}if ans == math.MaxInt32 {return 0}return ans
}func min(x, y int) int {if x < y {return x}return y
}

时间复杂度：$O(n^2)$
空间复杂度：$O(1)$

滑动窗口

接下来就开始介绍数组操作中另一个重要的方法：滑动窗口。

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

在暴力解法中，是一个for循环遍历滑动窗口的起始位置，一个for循环为寻找滑动窗口的终止位置，用两个for循环 完成了一个不断搜索区间的过程。

那么滑动窗口如何用一个for循环来完成这个操作呢。

首先要思考 如果用一个for循环，那么这个for循环移动应该表示 滑动窗口的起始位置，还是终止位置。

如果只用一个for循环来表示 滑动窗口的起始位置，那么如何遍历剩下的终止位置？

此时难免再次陷入 暴力解法的怪圈。

所以 只用一个for循环，那么这个循环的索引，一定是表示 滑动窗口的终止位置。

那么问题来了， 滑动窗口的起始位置如何移动呢？后文解答如果动态调整。

其实不难发现滑动窗口也可以理解为双指针法的一种！只不过这种解法更像是一个窗口的移动，所以叫做滑动窗口更适合一些。

在本题中实现滑动窗口，主要确定如下三点：

• 窗口内是什么？
• 如何移动窗口的起始位置？
• 如何移动窗口的结束位置？

窗口就是 满足其和≥ s的长度最小的 连续 子数组。

窗口的起始位置如何移动：如果当前窗口的值大于等于s了，窗口就要向前移动了（也就是该缩小了）。

窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

解题的关键在于 窗口的起始位置如何移动，如图所示：

此块代码的精髓就是在不断动态调整窗口的起始位置

for sum >= target && slow < len(nums) {// 不断减小的过程中还是可能一直大于等于target的，所以上面是for，而非ifif (fast - slow + 1) < res {res = fast - slow + 1}sum -= nums[slow]slow++}

可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将$O(n^2)$暴力解法降为$O(n)$。

Go代码如下：

func minSubArrayLen(target int, nums []int) int {//  双指针滑动窗口做法，slow指向当前窗口起点，fast不断后移，达到当前窗口之和大于target时，更新结果if len(nums) == 0 {return 0}slow,fast,sum,res := 0,0,0,math.MaxInt32 // 因为要找较小值，所以res先设置一个较大值for fast < len(nums) {sum += nums[fast]// 当前窗口已经大于等于target，fast继续后移会一直大于等于了// 所以此时应该移动slow，直到小于target为止，而后以最新的slow为起点，找满足条件的新的连续子数组for sum >= target && slow < len(nums) {// 不断减小的过程中还是可能一直大于等于target的，所以上面是for，而非ifif (fast - slow + 1) < res {res = fast - slow + 1}sum -= nums[slow]slow++}fast++}// 如果退出上述for时，res还是最大值，即res从未更新过，应该返回0，没有找到任何子数组if res == math.MaxInt32 {return 0}return res
}

时间复杂度：$O(n)$
空间复杂度：$O(1)$

一些朋友会疑惑为什么时间复杂度是$O(n)$。

不要以为for里放一个for就是认为是O(n^2)啊， 主要是看每一个元素被操作的次数，每个元素在滑动窗口中进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)。

904. 水果成篮

904. 水果成篮

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

提示：

$1<=fruits.length<=10^5$
$0<=fruits[i]<fruits.length$

思路：
双指针滑动窗口做法:理清下面四个内容，思路就清晰了

• 窗口内容：只有两种类型的果树，使用哈希表存储这个窗口内的数以及出现的次数。

• 外层for循环为寻找窗口的终点:我们每次将 right 移动一个位置，并将 fruits[right] 加入哈希表并计数加1。

• 内层也会有个for，不断缩小符合条件的窗口，即窗口的起点后移，寻找以该位置为起点的新的符合条件的窗口。因此内层for循环的作用为判断如果此时哈希表不满足要求（即哈希表中出现超过两个键值对），那么我们需要不断移动 left，将fruits[left] 在哈希表中的计数不断减小，直到为0，并将 fruits[left] 从哈希表中移除。

例如出现[1,2,1,1,2,3,3,4]时，当摘到类型为3的水果时，需要将类型为1的水果都删除，但第二个位置有个类型为2的水果，也要计数减1（Map中对应2的水果类型计数减1，2类型水果比1类型水果后加入Map，所以计数一定会后变为0的，因此符合该轮删除的是1类型水果的诉求）

• 结果：符合条件的最大窗口长度

Go代码

func totalFruit(fruits []int) (ans int) {cnt := map[int]int{}left := 0for right, x := range fruits {cnt[x]++for len(cnt) > 2 {y := fruits[left]cnt[y]--if cnt[y] == 0 {delete(cnt, y)}left++}ans = max(ans, right-left+1)}return
}func max(a, b int) int {if b > a {return b}return a
}

76. 最小覆盖子串

76. 最小覆盖子串

给你一个字符串 s 、一个字符串t。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖t所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果s中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s 和 t 由英文字母组成

进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

思路：
本问题要求我们返回字符串 s 中包含字符串 t 的全部字符的最小窗口。我们称包含t的全部字母的窗口为「可行」窗口。

我们可以用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的r指针，和一个用于「收缩」窗口的 l 指针。在任意时刻，只有一个指针运动，而另一个保持静止。我们在s上滑动窗口，通过移动r指针不断扩张窗口。当窗口包含 t 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。

如何判断当前的窗口包含所有 t 所需的字符呢？我们可以用一个哈希表表示 t 中所有的字符以及它们的个数，用一个哈希表动态维护窗口中所有的字符以及它们的个数，如果这个动态表中包含 t 的哈希表中的所有字符，并且对应的个数都不小于t的哈希表中各个字符的个数，那么当前的窗口是「可行」的。

注意：这里 t 中可能出现重复的字符，所以我们要记录字符的个数。

下面是一个好理解的版本，但是在反复的获取Map，提交的时候会出现超时，这里贴出代码，主要是看上去思路比较清晰。

Go代码

func minWindow(s string, t string) string {/*窗口内容：包含t的所有字符（对于t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。）外层for循环：寻找子串的终点内层for循环：不断移动，定位到下一个窗口的起点结果：最小子串*/if s == "" {return ""}left,right,res,maxLen := 0,0,"",math.MaxInt32for right = 0;right <= len(s);right++{// 未包含t所有字符时，窗口终点右移if !check(s[left:right],getCharsMap(t)) {continue}for left < right {if check(s[left:right],getCharsMap(t)) {if len(s[left:right]) < maxLen {res = s[left:right]maxLen = len(res)}  left++ } else{break}}}if maxLen == math.MaxInt32 {return ""}return res
}// 获取所有字符出现的次数
func getCharsMap(s string) map[rune]int{res := make(map[rune]int)for _,c := range s {res[c]++}return res
}// str中是否包含了Map中所有的字符(含重复出现的)
func check(str string,m map[rune]int) bool {for _,c := range str {if _,ok := m[c];ok { m[c]--}}for _,v := range m {if v > 0 {// t中的字符还有没被消掉的，说明当前窗口没有包含t的所有字符（重复字符算多个字符）return false}}return true
}

思路中提到的计数版本

Go代码

func minWindow(s string, t string) string {ori, cnt := map[byte]int{}, map[byte]int{}for i := 0; i < len(t); i++ {ori[t[i]]++}sLen := len(s)len := math.MaxInt32ansL, ansR := -1, -1check := func() bool {for k, v := range ori {if cnt[k] < v {return false}}return true}for l, r := 0, 0; r < sLen; r++ {if r < sLen && ori[s[r]] > 0 {cnt[s[r]]++}for check() && l <= r {if (r - l + 1 < len) {len = r - l + 1ansL, ansR = l, l + len}if _, ok := ori[s[l]]; ok {cnt[s[l]] -= 1}l++}}if ansL == -1 {return ""}return s[ansL:ansR]
}