leetcode 76. 最小覆盖子串

2023.10.14

        本题利用滑动窗口+哈希表来做。先定义start和end指针来维护滑动窗口，end不断扩展滑动窗口，start不断收缩。期间利用哈希表来判断当前窗口是否覆盖目标字符串t。

        具体java代码如下：

class Solution {
    public String minWindow(String s, String t) {
        Map map1 = new HashMap<>();
        Map map2 = new HashMap<>();
        String ans = "";
        //将字符串t的字符以及出现次数映射到哈希表中
        for(int i=0; i
            map1.put(t.charAt(i) , map1.getOrDefault(t.charAt(i),0) + 1);
        }
        int start = 0;
        int end = 0;
        int sum = 0;
        while(end < s.length()){
            map2.put(s.charAt(end),map2.getOrDefault(s.charAt(end),0) + 1);
            if(map2.getOrDefault(s.charAt(end),0) <= map1.getOrDefault(s.charAt(end),0)) sum++;
            while(start0)>map1.getOrDefault(s.charAt(start),0)){
                map2.put(s.charAt(start),map2.getOrDefault(s.charAt(start),0)-1);
                start++;
            }
            if(sum == t.length()){
                if(ans.length()==0 || end-start+1 < ans.length()){
                    ans = s.substring(start,end+1);
                }
            }
            end++;
        }
        return ans;
    }
}

        代码写起来还是有难度的，日后二刷。