力扣labuladong——一刷day10

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

一、力扣76. 最小覆盖子串

class Solution {public String minWindow(String s, String t) {Map<Character,Integer> need = new HashMap<>();Map<Character,Integer> window = new HashMap<>();for(char c : t.toCharArray()){need.put(c,need.getOrDefault(c,0)+1);}int left = 0, right = 0, indexLeft = 0, len = Integer.MAX_VALUE, vaild = 0;while(right < s.length()){char c = s.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(vaild == need.size()){//更新收集结果if(right - left < len){len = right - left;indexLeft = left;}char cur = s.charAt(left);left ++;//缩小窗口if(need.containsKey(cur)){if(need.get(cur).equals(window.get(cur))){vaild --;}window.put(cur,window.get(cur)-1);}}}return len == Integer.MAX_VALUE ? "" : s.substring(indexLeft,indexLeft+len);}
}

二、力扣567. 字符串的排列

class Solution {public boolean checkInclusion(String s1, String s2) {Map<Character,Integer> need = new HashMap<>();Map<Character,Integer> window = new HashMap<>();for(char c : s1.toCharArray()){need.put(c,need.getOrDefault(c,0)+1);}int left = 0, right = 0, vaild = 0; boolean flag = false;while(right < s2.length()){char c = s2.charAt(right);right ++;if(need.containsKey(c)){window.put(c,window.getOrDefault(c,0)+1);if(need.get(c).equals(window.get(c))){vaild ++;}}while(right - left >= s1.length()){if(vaild == need.size()){return true;}char cur = s2.charAt(left);left ++;if(need.containsKey(cur)){if(need.get(cur).equals(window.get(cur))){vaild --;}window.put(cur,window.get(cur)-1);}}}return false;}
}

三、力扣438. 找到字符串中所有字母异位词

class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer> res = new ArrayList<>();Map<Character, Integer> need = new HashMap<>();Map<Character, Integer> window = new HashMap<>();for(char c : p.toCharArray()){need.put(c,need.getOrDefault(c,0)+1);}int left = 0, right = 0, vaild = 0;while(right < s.length()){//窗口扩大char c = s.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 >= p.length()){//收集if(vaild == need.size()){res.add(left);}//缩小窗口char cur = s.charAt(left);left ++;//调整窗口if(need.containsKey(cur)){if(window.get(cur).equals(need.get(cur))){vaild --;}window.put(cur,window.get(cur)-1);}}}return res;}
}

四、力扣3. 无重复字符的最长子串

class Solution {public int lengthOfLongestSubstring(String s) {int res = 0;Map<Character, Integer> window = new HashMap<>();int left = 0, right = 0;while(right < s.length()){char c = s.charAt(right);right ++;window.put(c,window.getOrDefault(c,0)+1);while(window.get(c) > 1){char cur = s.charAt(left);left ++;window.put(cur,window.get(cur)-1);}res = Math.max(res,right-left);}return res;}
}