---

前言

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-window-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

滑动窗口加欠债表

窗口有单调性
str1范围变大,能搞定str2的数量一定只会变多不会变少


窗口向右扩一个
map中b的个数–. ,有效还款, all–

继续, b-1,无效还款，a不要变

all=0的时刻,代表如果子串必须以0开头的话，它到5才刚刚好能包含下所有str2。
在必须以0开头的情况下，多长的子串能够还完, 6长度

窗口缩一个,b++

all只要不是0, right边界就给我扩去。
如果是0, right边界停, L边界开始往右缩，所有答案求出来,最小值就是答案。

代码

class Solution {
    public String minWindow(String s, String t) {
        if(s.length()<t.length()){
            return "";
        }
        char[] str=s.toCharArray();
        char[] target=t.toCharArray();
        int[] map=new int[256];
        for(char cha:target){
            map[cha]++;
        }
        int all=target.length;
        int l=0;
        int r=0;
        int minLen=-1;
        int ansl=-1;
        int ansr=-1;
        while(r!=str.length){
            map[str[r]]--;
            if(map[str[r]]>=0){
                all--;
            }
            if(all==0){
                while(map[str[l]]<0){
                    map[str[l++]]++;
                }
                if(minLen==-1||minLen>r-l+1){
                    minLen=r-l+1;
                    ansl=l;
                    ansr=r;
                }
                all++;
                map[str[l++]]++;
            }
            r++;
        }
        return minLen == -1 ? "" : s.substring(ansl, ansr + 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39