- 1this.$router.push（）两种传参和参数接收_router.push传值接收值
- 2除夕团圆夜
- 3ncnn matlab,1M人脸检测模型(含关键点)
- 4头像裁剪【微信小程序、uni-app】_uni-cropper
- 5SpringBoot Redis入门（一）——redis、Lettuce、Redisson使用_spring redis lettuce
- 6android 5.0 lg g2,升级到Android 5.0 的LG G2怎样Root？
- 7【异常】Caused by: java.lang.ClassNotFoundException: org.springframework.dao.DataIntegrityViolationExcep...
- 8鸿蒙Harmony应用开发—ArkTS声明式开发（基础手势：Web）下篇
- 9Java:实现简单的计算器(加减乘除)_java编写简易计算器实现加减乘除
- 10通过fail2ban服务监控frps日志实现禁止非法IP
【LeetCode】滑动窗口系列总结_滑动窗口leetcode
赞
踩
滑动窗口系列总结
参考：
LeetCode刷题顺序
滑动窗口类型(Sliding window)
labuladong的滑动窗口模版
用到滑动窗口的题目类型
关于求最长/最小 子串之类的
或者特定长度的要求
滑动窗口模版
滑动窗口的思想：维护一个left、right 然后right右移扩张窗口，直到right到最右边停止。left右移就是收缩窗口，收缩窗口的条件为此时窗口满足题目要求了。
- 窗口右移时要做的事:
- 判断是否为答案需要的，是need需要的就更新进窗口
- 要注意更新目前进度，用来判断窗口内数据是否已满足条件
- 当窗口内的数据满足条件 窗口左移，如何判断窗口内的数据满足条件
- 这个条件就是 扩张窗口和收缩窗口时要更新的
比如找最小字符串时用valid来记录窗口内满足条件的字符个数，扩张窗口的时候valid++，收缩窗口时valid–
- 这个条件就是 扩张窗口和收缩窗口时要更新的
- 窗口满足条件后，进行窗口左移
- 左移过程中，如果左移后就不满足条件了说明找到一个解了
java模板：
void slidingWindow(String s,String t){ HashMap<Character,Integer> need = new HashMap<Character, Integer>();//need 是需要凑齐的字符 HashMap<Character,Integer> window = new HashMap<Character, Integer>(); // window是窗口中的字符 // 把t中 每个字符出现的次数记录到need中 for(int i = 0;i<t.length();i++){ need.put(t.charAt(i),need.getOrDefault(t.charAt(i),0)+1); } int left=0,right=0; // 滑动窗口的边界 int valid = 0; //窗口中满足need条件的字符个数 //找到最右边 while(right<s.length()){ //c是即将移入窗口的字符 Character c = s.charAt(right); //增加right指针扩大窗口 right++; // 进行窗口内数据的更新 ... /** 如果当前c是窗口需要的 则添加进窗口 对window进行操作 */ //需要收缩窗口 while(收缩窗口的条件){ //答案可能更新的位置1 ... //d是即将移出窗口的字符 Character d = s.charAt(left); //增加left指针缩小窗口 left++; // 进行窗口的更新 ... /** 对window进行操作 */ //答案可能更新的位置w ... } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
-
扩张窗口时（right++） 如何更新窗口数据
-
收缩窗口的条件
-
收缩窗口时（left–）如何更新窗口数据
一般收缩和扩张更新数据都是对应的 -
注意更新答案的地方：
明确我们需要的答案在哪部分，例如3.无重复最长子串，我们需要的答案就是在收缩完窗口才保证窗口内没有重复的串，这时更新答案最合适
76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
示例 2：
输入：s = “a”, t = “a”
输出：“a”
提示：
1 <= s.length, t.length <= 105
s 和 t 由英文字母组成
进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
思路：
- 当扩大窗口的时候，如果即将移入窗口的字符包含在need中，我们就要对window进行更新，更新后如果window里该字符的数量已经满足需求即和need中该字符的数量相等，valid就要++；
- 当已经找到可行解，即valid的值和need值相等 就要开始收缩窗口
- 收缩窗口时，首先如果当前len比之前的len更小则更新len；然后就是对window进行更新，更新前如果window里该字符的数量已经满足需求即和need中该字符的数量相等，valid就要–；
需要注意的是，我们判断wind和need中字符个数不能用==而要用equals，因为我们定义的Map里的Integer是对象，Integer会缓存频繁使用的数值[-128,127]，超过此范围就会new一个对象，导致使用“==”错误
class Solution { public String minWindow(String s, String t) { HashMap<Character,Integer> need = new HashMap<Character, Integer>();//need 是需要凑齐的字符 HashMap<Character,Integer> window = new HashMap<Character, Integer>(); // window是窗口中的字符 // 把t中 每个字符出现的次数记录到need中 for(int i = 0;i<t.length();i++){ need.put(t.charAt(i),need.getOrDefault(t.charAt(i),0)+1); } int left=0,right=0; // 滑动窗口的边界 int valid = 0; //窗口中满足need条件的字符个数 int start = 0,len = Integer.MAX_VALUE; //最小覆盖子串的起始索引和长度 //找到最右边 while(right<s.length()){ //c是即将移入窗口的字符 Character c = s.charAt(right); //增加right指针扩大窗口 right++; // 进行窗口内数据的更新 if(need.containsKey(c)){ window.put(c,window.getOrDefault(c,0)+1); if(window.get(c).equals(need.get(c))){ valid++; } } //需要收缩窗口： window里已经包含了t中所有字符，即找到了可行解，接下来找最优解 while(valid==need.size()){ //当前满足条件的最小子串 的长度比之前小 则更新 if((right-left)<len){ start = left; len = right-left; } //d是即将移出窗口的字符 Character d = s.charAt(left); //增加left指针缩小窗口 left++; // 进行窗口的更新 if(need.containsKey(d)){ if(window.get(d).equals(need.get(d))){ valid--; } window.put(d,window.get(d)-1); } } } return len==Integer.MAX_VALUE?"":s.substring(start,start+len); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
排列相关
- 字符串排列
- 找到字符串中所有字母异位词
这两道题几乎是一样的
567. 字符串排列
567. 字符串排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
示例 1：
输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).
示例 2：
输入: s1= “ab” s2 = “eidboaoo”
输出: False
提示：
输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间
思路：
这道题的特点是找到最小的排列，那么我们收缩窗口的条件应该是当前窗口的长度大于等于s1的长度
返回true的条件就是valid和need的长度相等
class Solution { public boolean checkInclusion(String s1, String s2) { HashMap<Character,Integer> need = new HashMap<Character,Integer>(); HashMap<Character,Integer> window = new HashMap<Character,Integer>(); for(int i=0;i<s1.length();i++){ Character c = s1.charAt(i); need.put(c,need.getOrDefault(c,0)+1); } int left=0,right=0; int valid = 0; //满足条件的字符个数 while(right<s2.length()){ //即将移入窗口的字符 Character q = s2.charAt(right); right++; //进行窗口内数据的更新 if(need.containsKey(q)){ window.put(q,window.getOrDefault(q,0)+1); if(need.get(q).equals(window.get(q))){ valid++; } } // 需要收缩窗口: 由于是排列，所以窗口大小比s1大的时候就需要收缩 while(right-left>=s1.length()){ if(valid==need.size()){ //符合条件 return true; } // d是即将移出窗口的字符 Character d = s2.charAt(left); left++; if(need.containsKey(d)){ if(need.get(d).equals(window.get(d))){ valid--; } window.put(d,window.getOrDefault(d,0)-1); } } } return false; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
438. 找到字符串中所有字母异位词
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。
示例 1:
输入:
s: “cbaebabacd” p: “abc”
输出:
[0, 6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的字母异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的字母异位词。
示例 2:
输入:
s: “abab” p: “ab”
输出:
[0, 1, 2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的字母异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的字母异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的字母异位词。
思路：
和上一题是一样的，只不过需要用一个List来存所有满足条件的答案
class Solution { public List<Integer> findAnagrams(String s, String p) { HashMap<Character,Integer> need = new HashMap<Character,Integer>(); HashMap<Character,Integer> window = new HashMap<Character,Integer>(); List<Integer> ans = new ArrayList<>(); for(int i = 0;i<p.length();i++){ Character c = p.charAt(i); need.put(c,need.getOrDefault(c,0)+1); } int left=0,right=0; int valid = 0; while(right<s.length()){ Character q = s.charAt(right); right++; //更新窗口数据 if(need.containsKey(q)){ window.put(q,window.getOrDefault(q,0)+1); if(need.get(q).equals(window.get(q))){ valid++; } } //收缩窗口 while(right-left>=p.length()){ // 看当前窗口符合不符合答案 if(valid==need.size()){ ans.add(left); } Character d = s.charAt(left); left++; if(need.containsKey(d)){ if(need.get(d).equals(window.get(d))){ valid--; } window.put(d,window.getOrDefault(d,0)-1); } } } return ans; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
3. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
示例 4:
输入: s = “”
输出: 0
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
思路：
这道题是求无重复最长子串，所以我们扩张窗口时就将window的key+1。
收缩窗口的条件就是遇到重复的key(window里此key的值大于1).
注意更新答案是在收缩窗口结束后，因为我们需要的是最长无重复子串，保证窗口中的子串没有重复就是收缩完窗口
class Solution { public int lengthOfLongestSubstring(String s) { HashMap<Character,Integer> window = new HashMap<Character,Integer>(); int left=0,right=0; int len = 0; while(right<s.length()){ Character c = s.charAt(right); right++; //更新窗口数据 window.put(c,window.getOrDefault(c,0)+1); //收缩窗口：包含重复的key while(window.get(c)>1){ Character d = s.charAt(left); left++; //更新窗口数据 if(window.containsKey(d)){ window.put(d,window.getOrDefault(d,0)-1); } } len = Math.max(len,right-left); } return len; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
904. 水果成篮
904. 水果成篮
在一排树中，第 i 棵树产生 tree[i] 型的水果。
你可以从你选择的任何树开始，然后重复执行以下步骤：
把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。
移动到当前树右侧的下一棵树。如果右边没有树，就停下来。
请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。
你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。
用这个程序你能收集的水果树的最大总量是多少？
示例 1：
输入：[1,2,1]
输出：3
解释：我们可以收集 [1,2,1]。
示例 2：
输入：[0,1,2,2]
输出：3
解释：我们可以收集 [1,2,2]
如果我们从第一棵树开始，我们将只能收集到 [0, 1]。
示例 3：
输入：[1,2,3,2,2]
输出：4
解释：我们可以收集 [2,3,2,2]
如果我们从第一棵树开始，我们将只能收集到 [1, 2]。
示例 4：
输入：[3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：我们可以收集 [1,2,1,1,2]
如果我们从第一棵树或第八棵树开始，我们将只能收集到 4 棵水果树。
提示：
1 <= tree.length <= 40000
0 <= tree[i] < tree.length
思路：
窗口的个数大于2 也就是篮子装不下了
注意收缩时 更新窗口的时候，要是当前key是0，要把它remove。
更新答案的地方是在收缩窗口结束后，因为这时窗口中是两种类型，即满足我们只有两个篮子的条件
class Solution { public int totalFruit(int[] tree) { HashMap<Integer,Integer> window = new HashMap<Integer,Integer>(); int left=0,right=0; int res = 0; while(right<tree.length){ //即将进入窗口的水果类型 int type = tree[right]; right++; //更新窗口数据 window.put(type,window.getOrDefault(type,0)+1); //收缩窗口： 窗口的个数大于2 也就是篮子装不下了 while(window.size()>2){ int d = tree[left]; left++; //更新窗口数据 window.put(d,window.getOrDefault(d,0)-1); if(window.get(d)==0){ window.remove(d); } } //此时 窗口中有两种类型，可以更新答案 res = Math.max(res,right-left); } return res; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
固定窗口
此类题的窗口都是固定长度的
第一步：将初始窗口压满，得到初始值
第二步：从左向右滑动窗口，每向右滑动一次则添加一个元素，删除一个元素
567 字符串的排列
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
示例 1：
输入：s1 = “ab” s2 = “eidbaooo”
输出：true
解释：s2 包含 s1 的排列之一 (“ba”).
示例 2：
输入：s1= “ab” s2 = “eidboaoo”
输出：false
提示：
1 <= s1.length, s2.length <= 10⁴
s1 和 s2 仅包含小写字母
解析：
- s2包含s1的排列，所以窗口的长度一定等于s1的长度，我们只需要用s1长度的窗口从左到右滑动即可，只要need和window的字母个数都一样则返回true。
- s1和s2仅包含小写字母，直接用26个字母数组来存储
class Solution { public boolean checkInclusion(String s1, String s2) { if (s1.length()>s2.length()){ return false; } int l1 = s1.length(); int l2 = s2.length(); int[] need = new int[26]; for (int i=0;i<l1 ;i++){ need[s1.charAt(i)-'a']++; } int[] window = new int[26]; for (int i=0;i<l1 ;i++){ window[s2.charAt(i)-'a']++; } if(check(need, window)){ return true; } // 滑动固定窗口 for (int i=l1;i<l2;i++){ window[s2.charAt(i)-'a']++; window[s2.charAt(i-l1)-'a']--; if(check(need, window)){ return true; } } return false; } public boolean check(int[] need, int[] window){ for (int i=0;i<26;i++){ if (need[i]!=window[i]){ return false; } } return true; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
643. 子数组最大平均数 I
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
任何误差小于 10⁻⁵ 的答案都将被视为正确答案。
示例 1：
输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
示例 2：
输入：nums = [5], k = 1
输出：5.00000
提示：
n == nums.length
1 <= k <= n <= 10⁵
-10⁴ <= nums[i] <= 10⁴
public double findMaxAverage(int[] nums, int k) {
int n = nums.length;
// 初始化最左窗口
double sum = 0.0;
for (int i = 0;i<k;i++){
sum+=nums[i];
}
double max =sum;
// 从左到右滑动窗口
for (int i=1;i<=n-k;i++){
sum = sum+nums[i+k-1]-nums[i-1];
max = Math.max(max,sum);
}
return max/k;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
-
串联所有单词的子串：【刷穿LC】朴素哈希表解法 + 滑动窗口解法
-
子数组最大平均数 I：滑动窗口裸题 （含模板）~
-
可获得的最大点数：详解滑动窗口基本思路（含模板）~
1423. 可获得的最大点数
几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
示例 1：
输入：cardPoints = [1,2,3,4,5,6,1], k = 3
输出：12
解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5
= 12 。
示例 2：
输入：cardPoints = [2,2,2], k = 2
输出：4
解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。
示例 3：
输入：cardPoints = [9,7,7,9,7,7,9], k = 7
输出：55
解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。
示例 4：
输入：cardPoints = [1,1000,1], k = 1
输出：1
解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。
示例 5：
输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
输出：202
提示：
1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length
思路：要左右两边拿的k张最大，也就是不被拿的n-k张最小，这样就可以用上面的模板来解题了
class Solution { public int maxScore(int[] cardPoints, int k) { // 求n-k张的总和最小 int n = cardPoints.length; int m = n-k; int sum = 0; int all = 0; // 总和 for (int i=0;i<n;i++){ all+=cardPoints[i]; } // 初始化窗口 for (int i=0;i<m;i++){ sum+=cardPoints[i]; } int min = sum; // 从左到右移动 for (int i=m;i<n;i++){ sum+=cardPoints[i]-cardPoints[i-m]; min = Math.min(min,sum); } return all-min; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
