滑动窗口经典题目解析【持续更新】-编程阁

1.无重复的最长子串

1.1题目链接

无重复的最长子串

1.2题目解析

直接right遍历整个数组,如果遇到不重复的就放进哈希表[字符和对应下标],如果遇到重复的就让left调整位置 ,一定要确保left到right之间的字符串是没有重复的,至于left跳到哪里就看到的重复字符是哪个,要取到一个当前left和当前right指向的字符在map存储的下标加一的较大值,如果重复字符的对应下标还是小于当前left的值那就不用管因为说明重复字符在left的左边,当前这个由right和left构成的窗口依然是合法_也就是不重复的.
所以哈希表的作用就是存储不重复字符的对应下标,以便于right在遇到重复字符left可以快速跳到需要的位置也就是保证left在当前right指向的重复字符的右边,
每次一遍流程结束之后就计算一下当前"窗口"的长度如果已经超过了最大长度就更新没有就不更.

1.3代码实现

classSolution{publicintlengthOfLongestSubstring(Strings){intlength=s.length();intmax_length=0;Map<Character,Integer>map=newHashMap<>();for(intleft=0,right=0;right<length;right++){charfgs=s.charAt(right);//不存在if(!map.containsKey(fgs)){map.put(fgs,right);}//存在else{left=Math.max(left,map.get(fgs)+1);map.put(fgs,right);}intnewLength=right-left+1;if(newLength>max_length){max_length=newLength;}}returnmax_length;}}

2.找到字符串中所有异位词

2.1题目链接

找到字符串中所有异位词

2.2题目解析

关键在于已知两个字符串怎么区比较他们是否相同,还要考虑字母顺序不同的情况,最简单的方法其实就是搞个哈希表,记录该字符串每个字符和对应出现的次数,如果都能对得上直接就判定他们是相同的.
所以我们其实可以先将p的字符串搞成一个目标哈希表,然后初始化一下窗口这个哈希表,注意长度要是目标哈希表的减一,然后for循环遍历s,进窗口就是那right对应字符放进哈希表 ,此时窗口哈希表的长度刚好符合目标哈希表,然后直接equals方法对比如果相同就说明当前窗口是异位词的子串,然后添加left即可
滑动的效果就是对比之后left向前走一步,同时将哈希表中left对应字符出现次数减一即可.(如果刚好是1就直接删除这个键值对).

2.3代码实现

classSolution{publicList<Integer>findAnagrams(Strings,Stringp){intsLength=s.length();intpLength=p.length();List<Integer>list=newArrayList<>();if(pLength>sLength){returnlist;}//初始化目标哈希表Map<Character,Integer>targetMap=newHashMap<>();for(inti=0;i<pLength;i++){charfgs=p.charAt(i);//不存在if(!targetMap.containsKey(fgs)){targetMap.put(fgs,1);}//存在else{targetMap.put(fgs,targetMap.get(fgs)+1);}}//初始化对比哈希表Map<Character,Integer>map=newHashMap<>();for(inti=0;i<pLength-1;i++){charjwy=s.charAt(i);if(!map.containsKey(jwy)){map.put(jwy,1);}//存在else{map.put(jwy,map.get(jwy)+1);}}//开始遍历s字符串for(intleft=0,right=pLength-1;right<sLength;right++){chardmm=s.charAt(right);if(!map.containsKey(dmm)){map.put(dmm,1);}//存在else{map.put(dmm,map.get(dmm)+1);}//开始对比if(targetMap.equals(map)){list.add(left);}//left出窗口if(map.get(s.charAt(left))==1){map.remove(s.charAt(left));}if(map.containsKey(s.charAt(left))){map.put(s.charAt(left),map.get(s.charAt(left))-1);}left++;}returnlist;}}