题目考察的知识点

滑动窗口

题目解答方法的文字分析

使用left和right来标志窗口左右边界。分别使用两个哈希表来记录指定字母的出现次数如果当前窗口包含了所有指定英文字母，则更新答案并尝试将窗口左端点向右移动；重复以上步骤 直到窗口不能再向右移动。

本题解析所用的编程语言

使用Java解答

完整且正确的编程代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param t string字符串
     * @return string字符串
     */
    public String minWindow (String s, String t) {
        // write code here
        int i, j, l, r, slen = s.length(), tlen = t.length(), remain;
        String res = "";
        if (slen >= tlen) {
            Map<Character, Integer> mp = new HashMap<>();
            for (i = 0; i < tlen; i++) {
                char c = t.charAt(i);
                mp.put(c, mp.getOrDefault(c, 0) + 1);
            }
            for (i = 0, j = 0, l = -1, r = -1, remain = tlen; j < slen; j++) {
                char c = s.charAt(j);
                if (mp.containsKey(c)) {
                    mp.put(c, mp.get(c) - 1);
                    if (mp.get(c) >= 0)
                        remain--;
                    if (remain == 0) {
                        for (; (remain == 0) && (i <= j); i++) {
                            char ch = s.charAt(i);
                            if (mp.containsKey(ch)) {
                                mp.put(ch, mp.get(ch) + 1);
                                if (mp.get(ch) > 0)
                                    remain++;
                            }
                        }
                        if (((l == -1) && (r == -1)) || (j - i < r - l)) {
                            l = i - 1;
                            r = j;
                        }
                    }
                }
            }
            if ((l != -1) && (r != -1))
                res = s.substring(l, r + 1);
        }
        return res;
    }
}