力扣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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

二、力扣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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

三、力扣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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

四、力扣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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19