力扣 76 二进制求和

题意：给定两个字符串s和t，找出s中能覆盖t的最短字符串

思路：具体见代码注释

思想：滑动窗口

复杂度：时间O（n)，空间O(n)

class Solution {
    public String minWindow(String s, String t) {
        // 记录t的字符出现的个数
        int[] map = new int[256];
        int m = s.length();
        int n = t.length();
        for(int i=0;i<n;i++) {
            map[t.charAt(i)]++;
        }
        if(m < n)
            return "";
        // 统计当前s中出现t的字符个数
        int cnt = 0;
        // 窗口的开始
        int start = 0;
        // 窗口的结束
        int end = 0;
        // 结果
        String res = "";
        // 当前最大长度
        int max = m + 1;
        while(end < m) {
            int cur = s.charAt(end++);
            // 字符未被统计过，加入cnt
            if(map[cur]>0) {
                cnt++;
            }
            // 把加入到窗口的字符从map中移除
            map[cur]--;
            // cnt ＝＝ n，缩小窗口直到cnt != n
            while(start<end && cnt == n) {
                // 当前字符串更小
                if(max > (end - start)) {
                    max = end - start;
                    res = s.substring(start, end);
                }
                int cur1 = s.charAt(start++);
                // 把移除窗口的字符加回到map中
                map[cur1]++;
                // 移除的字符为统计过的字符，cnt－－
                if(map[cur1] > 0)
                    cnt--;
            }
        }
        // 没有在s中找到合法的字符串返回“”
        if(max == m + 1)
            return "";
        return res;
    }
}