学校网站建设的背景,把网站制作成app,搭建网站服务器教程,快速建立网站思路#xff1a;滑动窗口思想
1. 滑动窗口是什么#xff1a;用一个滑动窗口为覆盖目标子串的字符串
2.怎么移动窗口#xff1a;当不满足覆盖时右指针移动扩大范围#xff0c;当覆盖了就移动左指针缩减范围直到再次不覆盖
3. 怎么判断是否覆盖#xff1a;这里使用两个哈…
思路滑动窗口思想
1. 滑动窗口是什么用一个滑动窗口为覆盖目标子串的字符串
2.怎么移动窗口当不满足覆盖时右指针移动扩大范围当覆盖了就移动左指针缩减范围直到再次不覆盖
3. 怎么判断是否覆盖这里使用两个哈希表一个保存目标子串字符数一个保存窗口内的字符数注意是窗口内的因为需要用窗口的和目标子串进行比较来控制移动
4. 怎么控制循环外层循环while(rightlen) right内层循环符合覆盖且leftright
class Solution {MapCharacter,Integer map new HashMapCharacter,Integer();MapCharacter,Integer target new HashMapCharacter,Integer();public String minWindow(String s, String t) {if(s.length() 1 s.equals(t)){return s;}int left 0;//初始化为-1int right -1;char[] str s.toCharArray();char[] tc t.toCharArray();//两个map一个保存目标串一个保存窗口值String res ;for(int i 0;itc.length;i){target.put(tc[i],target.getOrDefault(tc[i],0)1);}int min str.length;while(rightstr.length){right;if(rightstr.length)map.put(str[right],map.getOrDefault(str[right],0)1);while(isMatch()leftright){if(minright-left1){res s.substring(left,right1);min right - left 1;}map.put(str[left],map.getOrDefault(str[left],0)-1);left;}}return res;}public boolean isMatch(){Set entry target.entrySet();for(Object e : entry){Map.Entry o (Map.Entry) e;Integer val (Integer)o.getValue();Character key (Character)o.getKey();if(map.getOrDefault(key,0)val){return false;}}return true;}
}
