滑动窗口-438. 找到字符串中所有字母异位词

文章目录1.题解核心解题思路滑动窗口2.机考代码3.知识点讲解1. map.getOrDefault(key, defaultValue)2. map.put(key, value)3. map.containsKey(key)4. s.toCharArray()5. s.charAt(index)6. Scanner 相关机考必备力扣地址 中等438. 找到字符串中所有字母异位词本题代码感觉有点麻烦1.题解核心解题思路滑动窗口问题本质在字符串s中找到所有和p字母组成完全相同、仅顺序不同的子串返回它们的起始下标。算法选择滑动窗口双指针维护一个长度固定为 p.length ()的窗口在 s 上滑动用两个哈希表分别统计needp 中各字符需要的数量window当前窗口内各字符的数量用match记录已经满足数量要求的字符种类当match need.size()时说明当前窗口就是一个异位词执行流程右指针右移扩展窗口统计字符窗口长度等于 p 长度时判断是否匹配左指针右移收缩窗口移除字符统计全程只遍历 s 一次时间复杂度 O (n)classSolution{publicListIntegerfindAnagrams(Strings,Stringp){ListIntegerresultnewArrayList();if(s.length()p.length())returnresult;MapCharacter,IntegerneednewHashMap();for(charc:p.toCharArray())need.put(c,need.getOrDefault(c,0)1);MapCharacter,IntegerwindownewHashMap();intl0,r0;intmatch0;while(rs.length()){charcs.charAt(r);r;if(need.containsKey(c)){window.put(c,window.getOrDefault(c,0)1);if(window.get(c).equals(need.get(c)))match;}while(r-lp.length()){if(matchneed.size())result.add(l);chards.charAt(l);l;if(need.containsKey(d)){if(window.get(d).equals(need.get(d)))match--;window.put(d,window.get(d)-1);}}}returnresult;}}2.机考代码importjava.util.*;publicclassMain{publicstaticListIntegerfindAnagrams(Strings,Stringp){ListIntegerresultnewArrayList();// 边界s比p短不可能出现异位词直接返回空if(s.length()p.length()){returnresult;}// need记录p中每个字符需要的数量MapCharacter,IntegerneednewHashMap();for(charc:p.toCharArray()){// 有c就1没有就默认0再1need.put(c,need.getOrDefault(c,0)1);}// window记录当前滑动窗口内字符的数量MapCharacter,IntegerwindownewHashMap();intleft0,right0;// match已经满足数量要求的字符种类数intmatch0;// 右指针扩展窗口while(rights.length()){charcs.charAt(right);right;// 当前字符在p中存在才加入窗口统计if(need.containsKey(c)){window.put(c,window.getOrDefault(c,0)1);// 窗口内该字符数量 需要的数量匹配数1if(window.get(c).equals(need.get(c))){match;}}// 窗口长度 p长度时开始收缩左边界while(right-leftp.length()){// 所有字符种类都匹配记录起始索引if(matchneed.size()){result.add(left);}// 移除左边界字符chards.charAt(left);left;if(need.containsKey(d)){// 移除前刚好匹配移除后就不匹配了match--if(window.get(d).equals(need.get(d))){match--;}// 窗口内该字符数量-1window.put(d,window.get(d)-1);}}}returnresult;}publicstaticvoidmain(String[]args){ScannerscannernewScanner(System.in);// 输入格式输入两行第一行s第二行pStringsscanner.nextLine();Stringpscanner.nextLine();// 输出结果System.out.println(findAnagrams(s,p));}}3.知识点讲解1.map.getOrDefault(key, defaultValue)作用从 map 中取 key 对应的值有 key → 返回对应 value无 key → 返回你指定的默认值这里是 0目的避免null报错方便统计次数2.map.put(key, value)向 map 中存入键值对已存在 key 则覆盖更新不存在则新增3.map.containsKey(key)判断 map 中是否包含某个 key这里用来判断字符是否出现在 p 中不在则不用统计4.s.toCharArray()把字符串转为 char 数组方便遍历每一个字符5.s.charAt(index)获取字符串指定下标的字符时间 O (1)是字符串随机访问的标准用法6.Scanner相关机考必备new Scanner(System.in)开启控制台输入scanner.nextLine()读取一行输入