广东建设教育协会网站首页,wordpress优酷自适应,管理wordpress,网络营销成功的案例有哪些滑动窗口的定义#xff1a;
滑动窗口这一个技巧主要运用于处理数组问题上#xff0c;一般用于“子串”问题。精髓是#xff0c;维护一个里面装着元素的“窗口”#xff0c;在将新元素装进“窗口”的同时#xff0c;根据题意#xff0c;把不符合题意的元素踢出“窗口”。…滑动窗口的定义
滑动窗口这一个技巧主要运用于处理数组问题上一般用于“子串”问题。精髓是维护一个里面装着元素的“窗口”在将新元素装进“窗口”的同时根据题意把不符合题意的元素踢出“窗口”。
滑动窗口的模板
right:0
left:0
for rightlen(数组或字符串){n 数组[right]right1for (窗口需要收缩的时候判断){l 数组[left]...left1}
}
接下来看几道题目
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 : 0right : 0left : 0res : 10000000for right len(nums) {n : nums[right]right 1sum nfor sum target {sum - nums[left]res min(res, right-left)left 1}}if res 10000000 {return 0}return res
}Leetcode 3.无重复的最长字串
给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。 https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/ func lengthOfLongestSubstring(s string) int {right : 0left : 0res : 0check_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 1for check_dict[word] 1 {l : string(s[left])left 1check_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 : 0left : 0res : 0dict : make(map[int]int)for right len(fruits) {n : fruits[right]right1if _, exist : dict[n]; !exist {dict[n] 1} else {dict[n] 1}for len(dict) 2 {l : fruits[left]left 1dict[l] - 1if dict[l] 0 {delete(dict,l)}}if right-left res{res right-left}}return res
}
