题解 | #最小覆盖子串#

最小覆盖子串

1、题意重述

给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。

换句话说，即在字符串s中找一个最短子串，这个子串里面包含了t字符串中的所有字符。

2、思路整理

使用双指针的思想：

Step1:用两个指针left,right分别指向字符串s的开头，然后将right进行右移，直到[s[left],s[right]]区间内包含了t字符串的所有字符，同时对子串进行记录。

Step2：将left进行右移，直到[s[left],s[right]]区间内不含t字符串的所有字符。

Step3：将right进行右移，直到[s[left],s[right]]区间包含t字符串的所有字符，并对子串进行记录。

Step4：重复step2和step3的操作。

Step5：直到right指针移出s字符串，并返回最小长度的子串。

3、代码实现

public static String minWindow(String s, String t) {
        if (s == null || s == "" || t == null || t == "" || s.length() < t.length()) {
            return "";
        }
        //用来统计每个字符出现次数
        int[] ns = new int[128];
        //用来统计滑动窗口中每个字符出现次数
        int[] w = new int[128];

        for (int i = 0; i < t.length(); i++) {
            ns[t.charAt(i)]++;
        }

        int left = 0;
        int right = 0;

        String res = "";

        int count = 0;

        //用来记录最短需要多少个字符。
        int minLength = s.length() + 1;

        while (right < s.length()) {
            char ch = s.charAt(right);
            w[ch]++;
            if (ns[ch] > 0 && ns[ch] >= w[ch]) {
                count++;
            }

            //移动到不满足条件为止
            while (count == t.length()) {
                ch = s.charAt(left);
                if (ns[ch] > 0 && ns[ch] >= w[ch]) {
                    count--;
                }
                if (right - left + 1 < minLength) {
                    minLength = right - left + 1;
                    res = s.substring(left, right + 1);

                }
                w[ch]--;
                left++;

            }
            right++;

        }
        return res;
    }

4、复杂度分析

时间复杂度：一层循环，因此时间复杂度为$O(N)O(N)$。

空间复杂度：常数级内存地址空间，因此空间复杂度为$O(1)O(1)$。