【LeetCode 76】最小覆盖子串

妖狐艹你老母 2022-11-25 11:43 122阅读 0赞

#### 题目描述 ####

给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 **O(n) 的时间复杂度**内，从字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入：S = "ADOBECODEBANC", T = "ABC"
    输出："BANC"

提示：

如果 S 中不存这样的子串，则返回空字符串 “”。  
如果 S 中存在这样的子串，我们保证它是唯一的答案。

#### 解题思路 ####

这道题仍旧是使用**双指针+map**实现。

*  首先，定义一个map，将子串所需要的字符及其个数存贮在map中
 *  定义两个指针，来维护一个滑动窗口
 *  右指针往后移动，如果发现当前的右指针的值在map中存在，就map中该元素需要的个数减一，如果该元素需要的个数为0，那总需要的个数needType也减一
 *  如果需要的元素个数为0（也就是左右指针之间已经包含了所需字符），那么就向右移动左指针来缩小范围，同时如果map中需要该元素，就往其中加一，需求数也加一。
 *  在缩小范围的同时，截取两指针之间的字符串，找出最短的字符串即可

这里说的挺啰嗦的，直接看代码吧！

该算法的**时间复杂度为O(m+n)**，m和n分别是两个字符串的长度，所以符合题目要求的O(n)的时间复杂度。**空间复杂度是O(m)**，m是s字符串的长度。

#### 代码实现 ####

/** * @param {string} s * @param {string} t * @return {string} */
    var minWindow = function(s, t) { 
        let l = 0
        let r = 0
        const need = new Map() // 表示子串的字符及个数
        for(let i of t){ 
            need.set(i, need.has(i) ? need.get(i)+1 : 1 )
        }
        let needtype= need.size
        let res = ''
        // 移动右指针
        while(r< s.length){ 
            const c= s[r]
            // 如果右指针当前的值在子串中存在，则need中该字符数也-1 
            if(need.has(c)){ 
                need.set(c, need.get(c) - 1)
                if(need.get(c) === 0) needtype -= 1 //如果这个字符需要数为0，则需要的个数为-1
            }
            // 子串已包含所有需要的字符，用该循环来缩小字串的长度
            while(needtype === 0){ 
                // 截取子串，找出最小长度的子串
                const newRes = s.substring(l, r+1)
                if(!res || newRes.length < res.length) res = newRes
                const c2 = s[l]
                // 移动左指针，如果左指针在需要的子串里面，需求数就+1
                if(need.has(c2)){ 
                    need.set(c2, need.get(c2)+ 1 )
                    if(need.get(c2) === 1) needtype += 1
                }
                l += 1
            }
            r += 1
        }
        return res
    };

#### 提交结果 ####

![在这里插入图片描述][20200808160523240.png]

[20200808160523240.png]: /images/20221124/685fce70f3544ccfbb88cca435783091.png