滑动窗口的定义:
滑动窗口这一个技巧主要运用于处理数组问题上,一般用于“子串”问题。精髓是,维护一个里面装着元素的“窗口”,在将新元素装进“窗口”的同时,根据题意,把不符合题意的元素踢出“窗口”。
滑动窗口的模板:
right:=0
left:=0
for right<len(数组或字符串){
n = 数组[right]
right+=1
for (窗口需要收缩的时候,判断){
l = 数组[left]
...
left+=1
}
}
接下来看几道题目:
Leetcode 209.长度最小的子数组
https://leetcode.cn/problems/minimum-size-subarray-sum/
题目简介:找到长度最短的一个子数组。并且数组内数字的和>=target
题目分析:窗口不断扩大,当窗口里的元素的总和满足条件后(>=target),窗口缩小,即target减去窗口左端的数。然后再用一个变量记录窗口的大小,最小值随时更新。直接用模板就好了:
func min(i, j int) int {
if i >= j {
return j
} else {
return i
}
}
func minSubArrayLen(target int, nums []int) int {
sum := 0
right := 0
left := 0
res := 10000000
for right < len(nums) {
n := nums[right]
right += 1
sum += n
for sum >= target {
sum -= nums[left]
res = min(res, right-left)
left += 1
}
}
if res == 10000000 {
return 0
}
return res
}
文章来源地址https://www.toymoban.com/news/detail-805930.html
Leetcode 3.无重复的最长字串
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
func lengthOfLongestSubstring(s string) int {
right := 0
left := 0
res := 0
check_dict := make(map[string]int)
for right < len(s) {
word := string(s[right])
if _, exist := check_dict[word]; !exist {
check_dict[word] = 1
} else {
check_dict[word] += 1
}
right += 1
for check_dict[word] > 1 {
l := string(s[left])
left += 1
check_dict[l] -= 1
}
if right-left > res {
res = right - left
}
}
return res
}
LEETCODE 904.水果成篮
https://leetcode.cn/problems/fruit-into-baskets/description/
题目有点拗口,简单解释:“窗口内”只能含有两种数字。问窗口最长能有多长?
可以用一个字典来装元素。当字典中出现3种及以上数字时,开始收缩窗口。有一个要点,当元素的个数为“0”时,记得把键值对删除。
func totalFruit(fruits []int) int {
right := 0
left := 0
res := 0
dict := make(map[int]int)
for right < len(fruits) {
n := fruits[right]
right+=1
if _, exist := dict[n]; !exist {
dict[n] = 1
} else {
dict[n] += 1
}
for len(dict) > 2 {
l := fruits[left]
left += 1
dict[l] -= 1
if dict[l] == 0 {
delete(dict,l)
}
}
if right-left >res{
res = right-left
}
}
return res
}
文章来源:https://www.toymoban.com/news/detail-805930.html
到了这里,关于Leetcode with Golang 滑动窗口 Part1的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!