https://leetcode.cn/problems/minimum-window-substring/

    • 欠债表

    image.png
    all是欠款总数量
    image.png
    image.png
    image.png
    只要减减后，不小于0，就是有效还款，all也要减减，
    若小于0则是无效还款，all不变
    image.png
    image.png
    image.png
    image.png
    image.png

    第一次all变成0的时刻，记录窗口长度，此时窗口的含义是如果子串必须以0开头，至少多长才能包含所有的字符，
    后面的先别管，L开始缩
    image.png
    以1开头，记录窗口长度，然后L继续缩
    image.png
    欠款了, 让R往右继续
    。。。
    。。
    。。

    补充：coding细节， 窗口设置成左闭右开的，初始值就很容易设置， [0, 0) 就表示这个窗口一开始没数

    1.  public static String minWindow(String s, String t) {
    2.         if (s.length() < t.length()) {
    3.             return "";
    4.         }
    5.         char[] sStr = s.toCharArray();
    6.         char[] tStr = t.toCharArray();
    7.         //欠帐表
    8.         int[] map = new int[256];
    9.         //初始化欠帐表
    10.         for (char c : tStr) {
    11.             map[c]++;
    12.         }
    13.         int all = tStr.length;
    14.         int len = Integer.MAX_VALUE;
    15.         //窗口左闭右开,[0, 0)代表一开始还没数
    16.         int L = 0;
    17.         int R = 0;
    18.         int ansL = 0;
    19.         int ansR = 0;
    20.         for (R = 0; R < sStr.length; R++) {
    21.             if (--map[sStr[R]] >= 0) { //有效还款
    22.                 all--;
    23.             }
    24.             if (all == 0) { //可以更新答案了
    25.                 while (map[sStr[L]] < 0) { //尽可能收缩
    26.                     map[sStr[L++]]++;
    27.                 }
    28.                 if (len > (R - L + 1)) {
    29.                     len = R - L + 1;
    30.                     ansL = L;
    31.                     ansR = R;
    32.                 }
    33.                 //下一个窗口了, 此刻map[sStr[L]]肯定是>=0的
    34.                 map[sStr[L++]]++;
    35.                 all++;
    36.             }
    37.         }
    38.         return len == Integer.MAX_VALUE ? "" : s.substring(ansL, ansR + 1);
    39.     }