滑动窗口：解决力扣四道mid 美团字节常考题 Java题解
写在前边：看 面经 的时候发现 字节、美团 等一些大厂经常考 力扣第3题 [ 无重复的最长字串 ]，属于经典的滑动窗口了，今天整理一下滑动窗口的思路。
---------------------------------
滑动窗口
滑动窗口的核心：前后两个指针维护一个窗口，前后不断滑动，更新答案
这个算法的思路不算难,但是窗口一旦滑起来就开始手忙脚乱的，不知道哪个指针该动了。
先练习几道题，再进行规律总结。
常考面试题：
(熟练掌握acm模式) 会输入输出
思路：
1.定义一个Map,用来存放窗口中的元素，不断地进行更新；
2.定义两个指针（指路双指针https://www.nowcoder.com/discuss/914913?source_id=profile_create_nctrack&channel=-1 ）；对字符串进行操作
3.当滑动窗口不断进行扩张（right++）的时候，如果出现了重复的元素，使left++ 直到重复元素消失
4.输出使用Math.max(res,right-left)进行保存。
注：
①定义Map使用HashMap<key,value> hash；存放元素使用hash.put(key,value)方法，改变key的value值直接put(key,newValue)即可;获取value值使用hash.get(key), getOrDefault(c,0)指的是当存在c时获取c的value值,不存在c时默认为0。
②获取字符串的特定字符使用charAt(index),字符串的索引从0开始。
③Math.max(a,b)取a和b中较大的那个数。
import java.util.*;
class Solution {
public void Main(String []args){
Scanner sc=new Scanner(System.in);
String s =sc.nextLine();
System.out.println(lengthOfLongestSubstring(s));
}
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer> window=new HashMap<Character,Integer>();
int left=0,right=0;
int res=0;
while(right<s.length()){
char c=s.charAt(right);
right++;
window.put(c,window.getOrDefault(c,0)+1);
//判断左侧窗口是否要进行收缩
//当滑动窗口中出现了重复的字母时，left指针--；减到窗口中没有重复的字符，再进行下一次的循环
while(window.get(c)>1){
char d=s.charAt(left);
left++;
//更新窗口中的数据
window.put(d,window.get(d)-1);
}
//多次进行循环，找到最大的res
res=Math.max(res,right-left);
}
return res;
}
} 上边的题目只是对一个在一个字符串上进行滑动，接下来提高难度，下边这道题存在两个字符串S（source）和T（target），从S中找到只包含T中元素的子串。
力扣第567题 [ 字符串的排列] https://leetcode-cn.com/problems/permutation-in-string/
思路：
①定义一个Map记录窗口window在s2上滑动，定义nedd保存目标字符串（for each遍历存放）
②双指针(left&right)控制窗口在s2上滑动
③窗口右边：right++;当need中包含right指向的字符时，放入window；当字符的值和value都相当时，有效字符vaild++；
④窗口左边：判断窗口是否大于T的长度，大于时且这个left所指字符在window中,进行移除，并且left++;有效字符vaild--;
class Solution {
public boolean checkInclusion(String s1, String s2) {
//这道题是明显的滑动窗口，相当于从Source中找到一个子串，这个子串中只包含Target的所有元素，没有其他的字符。
Map<Character,Integer> window=new HashMap<>();
Map<Character,Integer> need=new HashMap<>();
char [] target=s1.toCharArray();
for(char c:target){
need.put(c,need.getOrDefault(c,0)+1);
}
int left=0,right=0;
int vaild=0;//vaild记录的是有效的字符串长度
while(right<s2.length()){
char c=s2.charAt(right);
right++;
if(need.containsKey(c)){
window.put(c,window.getOrDefault(c,0)+1);
if(window.get(c).equals(need.get(c))){
vaild++;
}
}
//判断左边窗口是否要进行收缩
while(right-left>=target.length){
//判断是否找到了合法的子串
if(vaild==need.size()){
return true;
}
char d=s2.charAt(left);
left++;
if(need.containsKey(d)){
if(window.get(d).equals(need.get(d))){
vaild--;
}
window.put(d,window.get(d)-1);
}
}
}
return false;
}
} 总结：滑动窗口框架 /* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
//一、定义存放窗口元素的位置的位置
Map<Character,Integer> window=new HashMap<>();
//有目标字符串就设置need，for each进行遍历target,放进need中
Map<Character,Integer> need=new HashMap<>();
char [] target=t.toCharArray();
for(char c:target){
need.put(c,need.getOrDefault(c,0)+1);
//二、设置左右指针，有效字符的个数，右指针不断进行++
int left = 0, right = 0;
int valid = 0;
//窗口右边
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s.charAt(right);
// 右移窗口
right++;
// 进行窗口内数据的一系列更新,具体情况具体分析，
//窗口左边： 判断左侧窗口是否要收缩
while (//不满足题目要求时) {
// d 是将移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新，具体情况具体分析
}
}
}
-----------------------------
推荐原文labuladong老师的https://mp.weixin.qq.com/s/ioKXTMZufDECBUwRRp3zaA，剩下的题目等考试回来再补
#笔试##实习##笔试题目##面经##Java#