LeetCode高频题76. 最小覆盖子串：欠账还债还款问题，子串考虑i开头的情况所有答案更新一波

提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题

---

文章目录

• LeetCode高频题76. 最小覆盖子串：欠账还债还款问题，子串考虑i开头的情况所有答案更新一波
• • @[TOC](文章目录)
• 题目
• 一、审题
• 二这题可不是动态规划，我试过，搞不出来，这题是欠账还款策略
• 代码细节
• 总结

题目

给你一个字符串 s 、一个字符串 t 。

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

注意：

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

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

---

一、审题

示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
示例 2：

输入：s = “a”, t = “a”
输出：“a”
示例 3:

输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

1 <= s.length, t.length <= 105
s 和 t 由英文字母组成

---

二这题可不是动态规划，我试过，搞不出来，这题是欠账还款策略

子串嘛，不就是考虑以i开头，或者结尾的情况

这不在乎顺序，咱就是要s包了t中的字符

长的s也行
短的子串也行
咱得找最短的那个子串，恰好包含t所有字符即可

不是啥动态规划，这个题就是欠债还款策略

o（n）拿下

（0）当s长度不够t，那包含失败了
（1）只有s长度N大于t长度M才行

建立欠账表【哈希表，数组也行】
map
记录所有字符，欠几个？？统计词频，拢共欠all个

整一个L–R把s中的子串包含进来，有的字符，还给map
只要map>=0，就是有效的还款
map<0可不行，这样就是多给你了字符

比如，下图
L–R范围内，多给了s有2个，无效还款
多给了一个b，无效还款

比如下图，本来还了一个c，又多出来一个c，还款无效，map中c那词频为负

当下面a换回来之后，你发现a还完了，all=0
all一旦是0，这时候就算是s已经整体把t包含了，因为你all全部还完了

目前啥含义？？
即：子串目前以L=0开头，最短的长度就是R-L+1，这样才能让all=0，还完了所有t的字符

不过呢，因为map还有负，所以就是说s中L–R包含的字符过多了
否则map咋变负了呢

必须以0开头的子串，让all=0，的长度min=R-L+1

好，我让L++，我们去找L=1开头的情况，它能否得到更短的答案
此时你发现s刚刚多还了一个，现在map中s变-1，说明我们把多还的s拿走

注意，此时all=0还是不变的，说明我们当前L–R范围内还是能还完t的所有字符
结算一个答案，更新给min=R-L+1

继续，我让L++，我们去找L=2开头的情况，它能否得到更短的答案
这时候你发现L–R吐出去a，但是这样的话，map又要欠款了，欠了a
all=1，说明又欠了
这时候不能结算结果，更新min，而是让R继续扩，看看能不能找到a换回来

总之，L从左到右，每一个位置i做一次开头，咱们让R使劲扩，直到我们还完all=0，就要更新一次答案

整体每次就是还款的事情，all=0结算，然后认为L++，让map恢复，all恢复，不断更新min

美滋滋

代码细节

map用数组，0–255空间，每个位置一个ASCII码
字符a–z就在里面的

要么R++，要么L++，咱们L,R永远不回头，所以就是o（n）一遍过

我们要的结果是子串
当结果最短时，我要把L位置记录一波，R记录一波
这样我们剪切L–R范围内的子串返回结果

设置窗口往往都是[L–R)左闭右开，右开那个R不算
L=0,R=0，最开始就没有拉进来，R即将要被扩进来

只要L处map还太多，可以提前先吐出去，保证L–R尽量短，同时也是包住t所有字符就行

最开始min长度设置为-1，表示还么有结算过，第一次结算就给它了
后续有更短的长度R-L+1，才有必要更新给min
当然，min直接用min函数更新即可

当all=0时，结算min之后，手动让L吐出去，此时人为让map把L这里欠款，all也欠

看代码：

        //复习:还款策略
        public String minWindowReview(String s, String t) {
            if(s.length() < t.length()) return "";

            //转字符数组，我们好操作
            char[] str = s.toCharArray();
            char[] ttr = t.toCharArray();
            //欠了t所哟字符
            int all = t.length();
            //统计词频
            int[] map = new int[256];
            for (int i = 0; i < ttr.length; i++) {
                map[ttr[i]]++;//t就是咱们要还的
            }

            int min = Integer.MAX_VALUE;//目前长度很长，无效
            int L = 0;
            int R = 0;//还款区间
            int ansL = 0;
            int ansR = 0;//中途发现有更短的长度就记录当前L--R，方便咱们回复结果

            while (R != str.length){//一旦R到达str末尾，说明所有情况都考虑了
                //R扩进来，换款，看看有效还款吗？
                map[str[R]]--;//还给t
                if (map[str[R]] >= 0) all--;//有效的还款，当map变负了就不行，还多了
                if (all == 0){
                    //刚刚好还完的话要结算了
                    //还之前咱们尽量让L缩短一点，否则结算太长没必要的,map为负就是L那边还太多，要拿走
                    while (map[str[L]] < 0) map[str[L++]]++;
                    //一旦缩到L--R已经是最短的了，看看此时长度是否更短了，或者第一次结算
                    if (R - L + 1 < min){
                        min = Math.min(min, R - L + 1);//更新最短长度
                        ansL = L;//记录这个就是当前找到的最短区间
                        ansR = R;
                    }
                    //结算之后，立马人为吐出L那个字符，人为欠债，探索别的L开头的可能性
                    map[str[L++]]++;//人为吐L，L++
                    all++;//L吐则必然欠债
                }
                //没还完还需R++继续换
                R++;
            }

            return min == Integer.MAX_VALUE ? "" : 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
40
41
42
43
44
45

最开始一来R=0，就是咱们要还款的字符位置，如果有效就让all–
如果all没有变0，还需要继续扩R

如果all=0了，说经已经L–R包含了所有t字符
此时，可能L那个位置是多还的字符，map为负，我们需要提前吐出来
保证L–R最短

直到map那是0，就代表恰好还完，而且L–R不能再缩小了
这样的话，就可以结算了
结算min有更小就要记录更小的位置ansL 和 ansR

之后，立马人为让L++，又增加all，欠债欠起来，探索新的L开头的答案会不会更短

持续玩下去，这样的话，就把所有可能的结果搞定了

测试：

    public static void test(){
        String s = "ADOBECODEBANC";
        String t = "ABC";
        Solution solution = new Solution();
        System.out.println(solution.minWindow(s, t));
        System.out.println(solution.minWindowReview(s, t));
    }


    public static void main(String[] args) {
        test();
    }
1
2
3
4
5
6
7
8
9
10
11
12

结果非常OK

BANC
BANC
1
2

LeetCode测试

速度够快吧，o（n）一遍搞定了就

关键在理解，map记录t中需要换的各个字符
all记录t长度，就是总体要还这么多

然L–R内扩R，一个个把all还了
map变负即使还多了，需要吐出来
然后整L–R既是最短的，又是各个好还完t所有字符，这样就可以结算一个结果给min
顺便记录L–R，用于返回结果
当所有L开头的情况，答案都考虑了，o（n）速度的结果也就出来了

---

总结

提示：重要经验：

1）本题不是动态规划，自然子串就是考虑所有位置i开头的答案，先建立欠债表，然后还债，刚刚还完就让L–R缩最短，然后认为欠债，考虑别的L开头的可能更短的答案；
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。