【LeetCode 算法专题突破】滑动窗口（⭐）

前言

学完了双指针算法，滑动窗口那肯定是逃不掉了，我个人感觉他俩就不分家，不把滑动窗口的题目好好刷上一刷我都难受

1. 长度最小的子数组

先来一道经典的滑动窗口试试水

题目链接：209. 长度最小的子数组

题目描述

其实滑动窗口题目的解法都大同小异，我们基本上写几道题目，就能很好的掌握这个算法的思想了，来看代码：

代码

func minSubArrayLen(target int, nums []int) int {sum, len, n := 0, math.MaxInt32, len(nums)left, right := 0, 0for right < n {sum += nums[right]for sum >= target {len = min(len, right-left+1)sum -= nums[left]left++}right++}if len == math.MaxInt32 {return 0}return len
}func min(a, b int) int {if a > b {return b}return a
}

我写滑动窗口的题目时，一般会按照这样一个步骤来编写代码：

1. 使用两个指针作为窗口的左右边界
2. 右边界往右延伸，数组内容进窗口
3. 左边界缩小范围，判断如何出窗口

这道题目相对容易，只需要关注 sum 和 target 是否匹配就行，之后遇到类似的题目就按照这样的解题思路来求解即可。

2. 无重复字符的最长子串

还是老样子，多做题，多思考，才能多进步

题目链接：3. 无重复字符的最长子串

题目描述

这道题目其实一眼看过去，有很多解法，可以直接通过暴力解出来，也可以用滑动窗口来进行匹配，直接通过 set 去重，我之前用 C++ 做这道题的时候就是这么做的，但是在题解区学习了一下之后，我也用上了一个很巧妙而且复杂度最低的方法，来看代码：

代码

func lengthOfLongestSubstring(s string) int {win := [128]bool{}left, len := 0, 0for right, v := range s {for win[v] == true { // 出现了重复的字符，开始循环去重（代码的核心）win[s[left]] = falseleft++}win[v] = truelen = max(len, right-left+1)}return len
}func max(a, b int) int {if a > b {return a}return b
}

这段代码可以说也是非常的清晰易懂，这个代码最核心最精华，或者说设计最巧妙的地方就是在他使用了一个 bool 类型的数组来完成去重操作，和滑动窗口的遍历完美融合到了一起。

3. 最大连续1的个数 III

让我们再来一道题目，操练一下使用滑动窗口的能力

题目链接：1004. 最大连续1的个数 III

题目描述

这道题目乍一看，会发现有很多种情况需要考虑，最重要的其实就是思考 K 个 0 该怎么翻转才能实现出最多的连续 1，来看代码：

代码

func longestOnes(nums []int, k int) int {left, cnt0, len := 0, 0, 0for right, v := range nums {if v == 0 {cnt0++}for cnt0 > k {if nums[left] == 0 {cnt0--}left++}len = max(len, right-left+1)}return len 
}func max(a, b int) int {if a > b {return a}return b
}

虽然题目分析起来似乎有很多中情况需要考虑，但是我们可以把问题巧妙的转化一下，从翻转 k 个 0 转化成允许 1 数组中存在 k 个 0，这样这道题目就只需要单纯的计算连续为 1 的数组，然后顺便记录一下数组中 0 的个数即可，这也是代码中的 cnt0 变量的由来~

4. 将 x 减到 0 的最小操作数

我们话不多说，继续来刷下一道题

题目链接：1658. 将 x 减到 0 的最小操作数

题目描述

乍一看，如果我们直接从两边找 target = x 的数感觉会很麻烦，代码也不好写，那我们该怎么做呢？来看代码：

代码

func minOperations(nums []int, x int) int {left, right, sum, lenth, target := 0, 0, 0, math.MaxInt32, -xfor _, v := range nums {target += v}if target < 0 { // 如果全加上都达不到要求就直接返回return -1}for right < len(nums) { sum += nums[right]right++for sum > target {sum -= nums[left]left++}if sum == target {lenth = min(lenth, len(nums)-(right-left))}}if lenth == math.MaxInt32 {return -1}return lenth
}func min(a, b int) int {if a > b {return b}return a
}

我们可以将问题转化一下，把问题转化成：找出最长的中间子数组，这样我们就能求出最少需要使用的步骤了，也就能使用滑动窗口来解题了，这里我们就是把 target 设置为：数组总和 - x，这样当我们的子数组和 sum == target 的时候，就是符合题目要求的情况了
做了几道滑动窗口的题目之后，我们发现其实滑动窗口算法真正难的不是代码的编写，代码写几遍发现都是同样的写法，真正有难度的是这么样把问题转化成可以使用滑动窗口算法的形式，那怎么样才能想到呢？没有捷径，只有多练，所以我们继续下一题~

5. 水果成篮

咱们继续来练习

题目链接：904. 水果成篮

题目描述

遇到像这种题目话很多的，其实不用管，直接抓关键词就行，读完题目其实很容易就能想到这道题目该怎么做了（有了前几道题目的经验），像这道题这样不需要转换问题思路就能直接做的，其实就非常简单了，来看代码：

代码

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

这里我们使用的是 map 来进行对水果数量的映射，这样比较方便，其实直接用一个数组来映射也是一样的。
咱们接着练习下一道题。

6. 找到字符串中所有字母异位词

题目链接：438. 找到字符串中所有字母异位词

题目描述

来看代码：

代码

func findAnagrams(s string, p string) (ans []int) {lens, lenp := len(s), len(p)if lenp > lens { // 如果 p 比 s 长就不用找了return}var wins, winp [26]intfor _, v := range p { winp[v-'a']++}left, right := 0, 0for right < lens {wins[s[right]-'a']++ // 入窗口right++if wins == winp {ans = append(ans, left)wins[s[left]-'a']-- // 出窗口left++}if right-left+1 > lenp {wins[s[left]-'a']-- // 出窗口left++}}return ans
}

这道题在我的解法中，需要注意的是，在我们缩窗口的时候记得要让 wins 的字母出窗口，所以就有两个需要出窗口的地方，让 wins 的大小和 winp 始终保持一致，这样就能把所有情况都比较一遍

7. 串联所有单词的子串

刷了这么多题目，最后必须得来一道 hard 证明一下自己~

题目链接：30. 串联所有单词的子串

题目描述

来看代码：

代码

func findSubstring(s string, words []string) (ans []int) {if len(words) == 0 {return ans}slen, wlen, clen := len(s), len(words), len(words[0])if slen < clen*wlen {return ans}cmp := map[string]int{}for _, v := range words { // 用于比较的 cmpcmp[v]++}for i:= 0; i < clen; i++ {cnt, win := 0, map[string]int{}for left, right := i, i; right <= slen-clen; right+=clen {word := s[right:right+clen] // 截取单词 word，一个个进行匹配if num, _ := cmp[word]; num != 0 { // 存在 word 这个单词for win[word] >= num { // 如果这个 word 数量超过预期，就出窗口win[s[left:left+clen]]--cnt--left+=clen}win[word]++ // 入窗口 + 计数cnt++} else { // 不存在 word 这个单词for left < right { // 比较中断了，全部 word 出窗口win[s[left:left+clen]]--cnt--left+=clen}left+=clen // 让 left = right 重新开始（因为最后 right 会 += clen）}if cnt == wlen {ans = append(ans, left)}}}return ans
}

这道题目的思路和上一道题非常的像，但是代码的编写难度要高不少，我还是使用一样的思路，对每一个单词进行比较，具体的操作流程如下：

1. 将需要比较的单词存进 cmp
2. 因为每个单词的长度相同，所以遍历 len(words) 就能得出所有情况
3. 接着设置 left，right 遍历整个 s
4. 然后就开始逐个单词进行匹配，再根据计数求是否符合题目要求

总结

滑动窗口专题的一些经典题目就告一段落啦，如果什么时候对滑动窗口算法的思路亦或者是写代码的方法有疑问，就可以回来重新刷一遍，相信日后再遇到能够使用滑动窗口的题目都能游刃有余，轻松解决~