前言
学完了双指针算法,滑动窗口那肯定是逃不掉了,我个人感觉他俩就不分家,不把滑动窗口的题目好好刷上一刷我都难受
1. 长度最小的子数组
先来一道经典的滑动窗口试试水
题目链接:209. 长度最小的子数组
题目描述
其实滑动窗口题目的解法都大同小异,我们基本上写几道题目,就能很好的掌握这个算法的思想了,来看代码:
代码
func minSubArrayLen(target int, nums []int) int {
sum, len, n := 0, math.MaxInt32, len(nums)
left, right := 0, 0
for 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
}
我写滑动窗口的题目时,一般会按照这样一个步骤来编写代码:
- 使用两个指针作为窗口的左右边界
- 右边界往右延伸,数组内容进窗口
- 左边界缩小范围,判断如何出窗口
这道题目相对容易,只需要关注 sum 和 target 是否匹配就行,之后遇到类似的题目就按照这样的解题思路来求解即可。
2. 无重复字符的最长子串
还是老样子,多做题,多思考,才能多进步
题目链接:3. 无重复字符的最长子串
题目描述
这道题目其实一眼看过去,有很多解法,可以直接通过暴力解出来,也可以用滑动窗口来进行匹配,直接通过 set 去重,我之前用 C++ 做这道题的时候就是这么做的,但是在题解区学习了一下之后,我也用上了一个很巧妙而且复杂度最低的方法,来看代码:
代码
func lengthOfLongestSubstring(s string) int {
win := [128]bool{}
left, len := 0, 0
for right, v := range s {
for win[v] == true { // 出现了重复的字符,开始循环去重(代码的核心)
win[s[left]] = false
left++
}
win[v] = true
len = 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, 0
for 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, -x
for _, 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, 0
for 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]int
for _, v := range p {
winp[v-'a']++
}
left, right := 0, 0
for 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 { // 用于比较的 cmp
cmp[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
}
这道题目的思路和上一道题非常的像,但是代码的编写难度要高不少,我还是使用一样的思路,对每一个单词进行比较,具体的操作流程如下:文章来源:https://www.toymoban.com/news/detail-722157.html
- 将需要比较的单词存进 cmp
- 因为每个单词的长度相同,所以遍历 len(words) 就能得出所有情况
- 接着设置 left,right 遍历整个 s
- 然后就开始逐个单词进行匹配,再根据计数求是否符合题目要求
总结
滑动窗口专题的一些经典题目就告一段落啦,如果什么时候对滑动窗口算法的思路亦或者是写代码的方法有疑问,就可以回来重新刷一遍,相信日后再遇到能够使用滑动窗口的题目都能游刃有余,轻松解决~文章来源地址https://www.toymoban.com/news/detail-722157.html
到了这里,关于【LeetCode 算法专题突破】滑动窗口(⭐)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!