算法攻关 - 最小覆盖子串 (O(n))

关注

发布于: 2021 年 03 月 02 日

一、题目描述

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

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

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

输入：s = "a", t = "a"
输出："a"

提示：

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

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

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

二、思考

基于第一篇我们讲过的指导篇，我们对于算法有了初步了解和认识，那么我们看这个题，初步想法是我们基于暴力破解法循环遍历，但是我们仔细思考下可以想到的是我们可以用双指针来代替一个 for 循环。因为这里要求的第一步是你能够解决这个问题，第二步是你能设计 O(n)时间复杂度的算法么？第一步参考官方答案即可，我们这里主要讲下第二种。

我们的核心思路如上图，希望使用滑动窗口的思想用双指针来解决这个问题，首先要处理条件情况一：固定左指针，移动右指针，如下

2.1、固定左指针，移动右指针

实现局部代码

 //4-1 处理右指针动，左指针不动情况        if (right+1<s.length() && count < t.length()){            //记录源字符串的字符元素            windows[s.charAt(right+1)]++;            //如果滑动窗口中的源字符元素个数小于需要的子字符串的元素个数            if (windows[s.charAt(right+1)] <= needs[s.charAt(right+1)]){                count++;            }            //右指针增加            right++;        }

复制代码

那么由题意可知我们需要的目标子字符串需要包含 A、B、C 三个元素。

1、将右指针 right 移动到如图黄色虚线位置的时候，你发现满足子字符串要求的 2 个条件，第一个是元素类型都满足我们用 count 记录，第二个是长度在原字符串可控范围内。

2、将滑动窗口的该字符元素值从 0 变为 1，如虚线图里面 A ->1 式例。是来标记每个元素出现的次数，防止如果出现重复元素的 case，无法处理的情况

3、如果滑动窗口中元素的出现的次数累加值与需要的子字符串元素的值相同，说明符合元素类型的 count 需要增加一个，反之不需要增加。

4、继续移动右指针。

2.2、固定右指针，移动左指针

如果 2.1 中的第一步已经不满足，则走 2.2 逻辑。

实现局部代码

{            //4-2 处理左指针动，右指针不动情况            //如果左指针到右指针的窗口大小 小于 最小滑动窗口，并且元素个数等同于子字符串长度            if (right-left+1 < minWindow && count == t.length()){                //记录下最小滑动窗口                minWindow = right -left +1;                finalLeft = left;                finalRight = right;
            }            //如果说源字符串数组大小 等于子字符串大小            if (windows[s.charAt(left)] == needs[s.charAt(left)]){                count--;            }            //源字符串减少            windows[s.charAt(left)]--;            //左指针增加            left++;        }

复制代码

不满足上述逻辑说明我们现在已经找到了局部最优解，那么这个时候如上图我们局部最优解目前是 ADOBEC。那么我们这个时候需要移动左指针来看下是否在这段范围内有更小的子串。

1、如果滑动窗口的大小小于当前局部最优解 minWindow，并且还符合 count 元素类型和个数，则认为当前的左右指针对应的子串为局部最优解，并记录下最左指针，最右指针。

2、如果说当前左指针元素比如图中的 A，正好是子字符串所需要的元素类型，那么 count 减少一个来表示我们左移动指针的时候丢掉了一个需要的元素字符

3、滑动窗口的元素个数也减少一个

4、左指针继续左移动

三、代码

public static String minWindow(String s, String t) {    //1-基础入参数校验，如果为空则直接不需要比较处理了    if (s== "" || t==""){        return "";    }    //2-初始化滑动窗口中用数组来保存变量    int[] needs = new int[128];    int[] windows= new int[128];    int left=0,right=-1,finalLeft=-1,finalRight=-1,minWindow=s.length()+1,count=0;    String res ="";
    //3-初始化子字符串需要的数组    for(int i=0;i<t.length();i++){        needs[t.charAt(i)]++;    }
    //4-退出循环条件为左指针移动到原字符串的最右端    while(left < s.length()){        //4-1 处理右指针动，左指针不动情况        if (right+1<s.length() && count < t.length()){            //记录源字符串的字符元素            windows[s.charAt(right+1)]++;            //如果滑动窗口中的源字符元素个数小于需要的子字符串的元素个数            if (windows[s.charAt(right+1)] <= needs[s.charAt(right+1)]){                count++;            }            //右指针增加            right++;        }else {            //4-2 处理左指针动，右指针不动情况            //如果左指针到右指针的窗口大小 小于 最小滑动窗口，并且元素个数等同于子字符串长度            if (right-left+1 < minWindow && count == t.length()){                //记录下最小滑动窗口                minWindow = right -left +1;                finalLeft = left;                finalRight = right;
            }            //如果说源字符串数组大小 等于子字符串大小            if (windows[s.charAt(left)] == needs[s.charAt(left)]){                count--;            }            //源字符串减少            windows[s.charAt(left)]--;            //左指针增加            left++;        }    }
    //5-如果最后的左指针不为初始值，则取最后的左指针到最后的右指针中间的字符串    if (finalLeft !=-1){        res = s.substring(finalLeft,finalRight+1);    }
    return res;}

复制代码

四、小结

主要逻辑在于时间复杂度为 O(t)+O(n) = O(n)。其实主要思想是固定一个指针，移动另外一个指针。

发布于: 2021 年 03 月 02 日阅读数: 17

原文链接:【http://xie.infoq.cn/article/409bc2c926305f9a9d931f89d】。文章转载请联系作者。

小诚信驿站

关注

小胜靠智，大胜靠德 2019.06.27 加入

历经创业、京东、腾讯、滴滴公司，希望能够有些东西一起分享。公众号：小诚信驿站，微信/CSDN搜索：wolf_love666

发布

暂无评论

创作场景

算法攻关 - 最小覆盖子串 (O(n))

一、题目描述

二、思考

2.1、固定左指针，移动右指针

2.2、固定右指针，移动左指针

三、代码

小诚信驿站

评论