题目描述

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

样例

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

说明：

• 如果 S 中不存这样的子串，则返回空字符串 ""。
• 如果 S 中存在这样的子串，我们保证它是唯一的答案。

算法分析

双指针

• 1、cnt维护的是s字符串[j,i]区间中满足t字符串的元素的个数（此题的主要精髓）
• 2、hs哈希表维护的是[j,i]区间中各个字符出现多少次，ht哈希表维护的是t字符串各个字符出现多少次
• 3、枚举过程中，将s[i]加入到hs中，同时观察s[j]是否多余，若多余则移出
• 4、将s[i]加入到hs中，若hs[i] <= ht[i]，表示多了一个符号的元素，cnt ++
• 5、若当前双指针维护的窗口满足个数要求，则更新答案

时间复杂度 $O(n)$

Java 代码

class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character,Integer> hs = new HashMap<Character,Integer>();
        HashMap<Character,Integer> ht = new HashMap<Character,Integer>();
        for(int i = 0;i < t.length();i ++)
        {
            ht.put(t.charAt(i),ht.getOrDefault(t.charAt(i), 0) + 1);
        }
        String ans = "";
        int len = 0x3f3f3f3f;
        int cnt = 0;//有多少个元素符合
        for(int i = 0,j = 0;i < s.length();i ++)
        {
            hs.put(s.charAt(i), hs.getOrDefault(s.charAt(i), 0) + 1);
            if(ht.containsKey(s.charAt(i)) && hs.get(s.charAt(i)) <= ht.get(s.charAt(i))) cnt ++;

            //维护双指针
            while(j < i && (!ht.containsKey(s.charAt(j)) || hs.get(s.charAt(j)) > ht.get(s.charAt(j))))
            {
                int count = hs.get(s.charAt(j)) - 1;
                hs.put(s.charAt(j), count);
                j ++;
            }

            if(cnt == t.length() && i - j + 1 < len)
            {
                len = i - j + 1;
                ans = s.substring(j,i + 1);
            }
        }
        return ans;
    }
}