题解 | #牛群名字覆盖#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param t string字符串
     * @return string字符串
     */

    public String minWindow(String s, String t) {
        // write code here
        Deque<Character> queue = new LinkedList<>();
        int count = t.length();
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);
        }
        int left = -1;
        int right = 0;
        String result = "";
        int len = Integer.MAX_VALUE;
        while (right < s.length()) {
            while (count != 0 && right < s.length()) {
                queue.addLast(s.charAt(right));
                if (map.containsKey(s.charAt(right))) {
                    map.put(s.charAt(right), map.get(s.charAt(right)) - 1);
                    if (map.get(s.charAt(right)) >= 0) {
                        count--;
                    }
                }
                right++;
            }
            if (right == s.length() && count != 0 && len == Integer.MAX_VALUE) {
                return "";
            }
            while (count == 0) {
                left++;
                queue.removeFirst();
                if (map.containsKey(s.charAt(left))) {
                    map.put(s.charAt(left), map.get(s.charAt(left)) + 1);
                    if (map.get(s.charAt(left)) > 0) {
                        count++;
                    }
                }
            }
            queue.addFirst(s.charAt(left));
            if (queue.size() < len) {
                StringBuffer stringBuffer = new StringBuffer();
                for (Character character : queue) {
                    stringBuffer.append(character);
                }
                result = stringBuffer.toString();
                len = result.length();
            }
            queue.removeFirst();
        }
        return result;
    }

}

本题考察的知识点是队列和双指针，所用编程语言是java。

利用队列主要是为了存储我们遍历的字符。首先我们需要明白如何找s中一个子字符串利用子字符串中的字符能够完全组成字符串t,我采用的方法选用哈希表加计数器。哈希表存储字符串t中每个字符出现的次数，计数器用来记录需要匹配的字符个数。我们遍历s中的每个字符串，如果哈希表中存在，则需要将对应出现的次数减一，然后判断此时哈希表中该字符的出现次数是否不小于0，如果不小于则计数器减一。当计数器为0时，则相应左指针开始移动，对应哈希表和计数器的操作相反。当计数器大于0时，则开始计算此时满足条件的字符串。然后继续相同操作，直到右指针到达s字符串末尾位置