地方网站 o2o,哈尔滨的网络科技开发公司,餐饮管理系统有哪些,php网页设计完整代码文章目录 前言1. 长度最小的子数组题目描述代码 2. 无重复字符的最长子串题目描述代码 3. 最大连续1的个数 III题目描述代码 4. 将 x 减到 0 的最小操作数题目描述代码 5. 水果成篮题目描述代码 6. 找到字符串中所有字母异位词题目描述代码 7. 串联所有单词的子串题目描述代码 … 文章目录 前言1. 长度最小的子数组题目描述代码 2. 无重复字符的最长子串题目描述代码 3. 最大连续1的个数 III题目描述代码 4. 将 x 减到 0 的最小操作数题目描述代码 5. 水果成篮题目描述代码 6. 找到字符串中所有字母异位词题目描述代码 7. 串联所有单词的子串题目描述代码 总结 前言
学完了双指针算法滑动窗口那肯定是逃不掉了我个人感觉他俩就不分家不把滑动窗口的题目好好刷上一刷我都难受
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-left1)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, 0for right, v : range s {for win[v] true { // 出现了重复的字符开始循环去重代码的核心win[s[left]] falseleft}win[v] truelen max(len, right-left1)}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-left1)}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]rightfor 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-left1)}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] // 入窗口rightif wins winp {ans append(ans, left)wins[s[left]-a]-- // 出窗口left}if right-left1 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; rightclen {word : s[right:rightclen] // 截取单词 word一个个进行匹配if num, _ : cmp[word]; num ! 0 { // 存在 word 这个单词for win[word] num { // 如果这个 word 数量超过预期就出窗口win[s[left:leftclen]]--cnt--leftclen}win[word] // 入窗口 计数cnt} else { // 不存在 word 这个单词for left right { // 比较中断了全部 word 出窗口win[s[left:leftclen]]--cnt--leftclen}leftclen // 让 left right 重新开始因为最后 right 会 clen}if cnt wlen {ans append(ans, left)}}}return ans
}这道题目的思路和上一道题非常的像但是代码的编写难度要高不少我还是使用一样的思路对每一个单词进行比较具体的操作流程如下
将需要比较的单词存进 cmp因为每个单词的长度相同所以遍历 len(words) 就能得出所有情况接着设置 leftright 遍历整个 s然后就开始逐个单词进行匹配再根据计数求是否符合题目要求
总结
滑动窗口专题的一些经典题目就告一段落啦如果什么时候对滑动窗口算法的思路亦或者是写代码的方法有疑问就可以回来重新刷一遍相信日后再遇到能够使用滑动窗口的题目都能游刃有余轻松解决~
