题解 | #最小覆盖子串 双指针#

import java.util.*;


public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String s, String t) {
        if (s.length() < t.length()){
            return "";
        }
        
        //maps是确定选中字符串分别包含目标字符的个数
        //mapt可以生成最小覆盖字串所需要的目标字符的个数
        HashMap<Character, Integer> maps = new HashMap<>();
        HashMap<Character, Integer> mapt = new HashMap<>();
        char[] ct = t.toCharArray();
        
        //maps、mapt的生成
        for (char c : ct) {
            maps.put(c, 0);
            if (mapt.containsKey(c)){
                mapt.put(c, mapt.get(c) + 1);
            }else {
                mapt.put(c, 1);
            }
        }
		//left、right用于判断substring(left, right + 1)是否合法
        int left = 0;
        int right = 0;
        char[] cs = s.toCharArray();
        int minLen = Integer.MAX_VALUE;
        String ans = "";

        while (right < cs.length) {
        
            if (maps.containsKey(cs[right])) {
                maps.put(cs[right], maps.get(cs[right]) + 1);
            }

            while (isValidArray(maps, mapt)) {
                if (minLen > right - left + 1){
                    minLen = right - left + 1;
                    ans = s.substring(left, right + 1);
                }
                if (maps.containsKey(cs[left])) {
                    maps.put(cs[left], maps.get(cs[left]) - 1);
                }
                left++;
            }

            right++;
        }
        return ans;
    }

//isValidArray 判断字符串中maps各字符是否到达最低要求mapt的要求 public static boolean isValidArray(HashMap<Character, Integer> maps,HashMap<Character, Integer> mapt) { for (Character character : maps.keySet()) { if (maps.get(character) < mapt.get(character)){ return false; } } return true; } }