高频面试算法题：如何求解最小覆盖子串问题

前端面试算法题中最小覆盖子串问题出现频率颇高，今天，咱们就来深入探讨这道题，并且会详细讲讲解题过程中用到的Map数据结构。要是你对Map不太熟悉，也别担心，下面会先介绍相关知识，再进入正题。

一、Map数据结构基础

（一）Map是什么

Map是JavaScript里一种用于存储键值对的集合。它和JavaScript中的普通对象有点像，但又存在一些重要差异：

键的类型：普通对象的键只能是字符串或者Symbol类型，而Map的键可以是任意数据类型，像对象、函数以及其他原始类型都没问题。
键的顺序：Map会记住键的插入顺序，遍历Map时，元素的顺序和插入时一致；普通对象则不保证键的顺序。
原型继承：Map没有原型，这样就不会意外获取到原型链上不属于它自身的数据。普通对象会从原型链继承属性和方法，可能引发一些意想不到的问题。
获取大小：使用size属性就能轻松获取Map的大小，也就是键值对的数量，不像普通对象还得手动计算。
性能：在频繁添加和删除键值对的场景下，Map的性能通常比普通对象更优。

（二）创建Map对象

创建Map对象有两种常见方式：

// 创建一个空Map const myMap = new Map(); // 创建一个包含初始键值对的Map (二维数组) const myMapWithValues = new Map([ ['key1', 'value1'], ['key2', 'value2'], [123, 'number_key'] ]);

上述代码中，第一种方式创建了一个空的Map；第二种方式通过传入一个二维数组，初始化了一个包含特定键值对的Map 。

（三）Map的常用方法

set(key, value)：用于添加或更新键值对。如果键不存在，就添加新的键值对；如果键已存在，则更新对应的值。

const myMap = new Map(); myMap.set('name', 'Alice'); myMap.set('age', 30); myMap.set('name', 'Bob'); // 更新 'name' 的值 console.log(myMap); // Map(2) { 'name' => 'Bob', 'age' => 30 }

get(key)：根据传入的键获取对应的值。要是键不存在，就返回undefined。

const myMap = new Map([['name', 'Charlie'], ['city', 'London']]); console.log(myMap.get('name')); // 输出: Charlie console.log(myMap.get('city')); // 输出: London console.log(myMap.get('country')); // 输出: undefined (键不存在)

has(key)：用来检查Map中是否包含指定的键，包含就返回true，否则返回false。

const myMap = new Map([['a', 1], ['b', 2]]); console.log(myMap.has('a')); // 输出: true console.log(myMap.has('c')); // 输出: false

delete(key)：删除指定键值对。如果删除成功，返回true；键不存在时，返回false。

const myMap = new Map([['x', 10], ['y', 20]]); console.log(myMap.delete('x')); // 输出: true (删除成功) console.log(myMap.delete('z')); // 输出: false (键不存在) console.log(myMap); // Map(1) { 'y' => 20 }

clear()：清空Map，让它变成一个空的Map。

const myMap = new Map([['p', 100], ['q', 200]]); myMap.clear(); console.log(myMap); // Map(0) {}

size：获取Map的大小，也就是键值对的数量。

const myMap = new Map([['apple', 1], ['banana', 2], ['cherry', 3]]); console.log(myMap.size); // 输出: 3

（四）遍历Map

Map提供了多种遍历方式：

keys()：获取所有键的迭代器，通过遍历这个迭代器，可以获取Map中所有的键。

const myMap = new Map([['a', 1], ['b', 2], ['c', 3]]); for (const key of myMap.keys()) { console.log(key); // 输出: a, b, c }

values()：获取所有值的迭代器，用于遍历获取Map中所有的值。

const myMap = new Map([['a', 1], ['b', 2], ['c', 3]]); for (const value of myMap.values()) { console.log(value); // 输出: 1, 2, 3 }

entries()：获取所有键值对的迭代器，返回的是[key, value]数组形式，方便同时获取键和值。

const myMap = new Map([['a', 1], ['b', 2], ['c', 3]]); for (const [key, value] of myMap.entries()) { console.log(key, value); // 输出: a 1, b 2, c 3 }

forEach(callbackFn, thisArg)：和数组的forEach类似，对Map中的每一个键值对执行传入的回调函数。

const myMap = new Map([['a', 1], ['b', 2], ['c', 3]]); myMap.forEach((value, key) => { console.log(key, value); // 输出: a 1, b 2, c 3 });

（五）Map的应用场景

Map在实际开发中有很多用途：

缓存：可以把计算结果存到Map里，这样遇到相同的计算时，直接从Map取结果，避免重复计算，提升程序效率。
键值对存储：当键的类型不确定，尤其是可能为对象时，Map比普通对象更适用。
维护插入顺序：在需要保证键的插入顺序的场景中，Map就派上用场了。
统计词频：利用Map能很方便地统计每个词出现的次数。
存储元数据：可以存储与DOM元素或其他对象相关的额外信息。

（六）Map与Object的选择

选择Map还是普通对象，可以参考以下原则：如果键始终是字符串或Symbol类型，并且对键的顺序没有要求，普通对象可能更简单；要是键的类型不确定，或者需要维护键的顺序，又或者频繁进行添加和删除键值对的操作，Map通常是更好的选择。

二、最小覆盖子串题目解析

（一）题目描述

给定两个字符串s和t，要求返回s中涵盖t所有字符的最小子串。如果s里不存在涵盖t所有字符的子串，就返回空字符串"" 。需要注意：

t中若有重复字符，寻找的子字符串中该字符数量不能少于t中该字符数量。
若s中存在满足条件的子串，确保它是唯一答案。

下面来看几个示例：

示例1：

输入： s = "ADOBECODEBANC", t = "ABC" 输出： "BANC" 解释： 最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例2：

输入： s = "a", t = "a" 输出： "a" 解释： 整个字符串 s 是最小覆盖子串。

示例3：

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

另外，题目还给出了一些限制条件：

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

进阶要求是设计一个能在o(m+n)时间内解决此问题的算法。

（二）题解：滑动窗口算法

/** * @param {string} s * @param {string} t * @return {string} */ var minWindow = function(s, t) { if (!s || !t || s.length === 0 || t.length === 0) { return ""; } const tMap = new Map(); // 存储 t 中每个字符出现的次数 for (const char of t) { tMap.set(char, (tMap.get(char) || 0) + 1); } let left = 0; // 滑动窗口的左指针 let right = 0; // 滑动窗口的右指针 let minLen = Infinity; // 最小子串的长度，初始化为无穷大 let start = 0; // 最小子串的起始位置 let matched = 0; // 记录窗口中满足 t 字符数量的字符个数 const windowMap = new Map(); // 存储滑动窗口中每个字符出现的次数 while (right < s.length) { const char1 = s[right]; // 获取右指针指向的字符 if (tMap.has(char1)) { // 如果该字符是 t 中需要的字符 windowMap.set(char1, (windowMap.get(char1) || 0) + 1); // 更新窗口中该字符的数量 if (windowMap.get(char1) === tMap.get(char1)) { // 如果窗口中该字符的数量已经满足 t 中该字符的数量，则 matched 加 1 matched++; } } right++; // 右指针右移 // 当窗口中所有 t 中的字符都满足数量时，尝试缩小窗口 while (matched === tMap.size) { // 更新最小子串 if (right - left < minLen) { minLen = right - left; start = left; } const char2 = s[left]; // 获取左指针指向的字符 if (tMap.has(char2)) { // 如果该字符是 t 中需要的字符 windowMap.set(char2, windowMap.get(char2) - 1); // 窗口中该字符的数量减 1 if (windowMap.get(char2) < tMap.get(char2)) { // 如果窗口中该字符的数量小于 t 中该字符的数量，则 matched 减 1 matched--; } } left++; // 左指针右移，缩小窗口 } } // 如果 minLen 没有被更新，则说明没有找到符合条件的子串 return minLen === Infinity ? "" : s.substring(start, start + minLen); };

1. 核心思想

这个算法运用了滑动窗口的思想。简单来说，就是在字符串s上维护一个动态大小的窗口，通过不断移动窗口的左右指针，在s中寻找满足条件的最小子串。这里的条件是窗口要包含字符串t中的所有字符，并且每个字符的数量不能少于t中对应字符的数量。

2. 详细步骤

初始化：
- 进行空值检查：如果s或t为空，直接返回空字符串"" ，因为空字符串肯定不存在满足条件的子串。
- 创建tMap：使用Map存储字符串t中每个字符出现的次数，这是后续判断窗口是否满足条件的重要依据。
- 初始化窗口指针：设置滑动窗口的左指针left为0，右指针right也为0 。
- 初始化结果变量：把minLen设为Infinity（无穷大），用于记录最小子串的长度；start设为0，用来标记最小子串的起始位置。
- 初始化匹配计数器：设置matched为0，它用来记录窗口中满足t字符数量要求的字符个数。
- 创建windowMap：使用Map存储滑动窗口中每个字符出现的次数。
扩展窗口 (移动右指针)：
- while (right < s.length)循环：不断移动右指针right遍历字符串s，每次循环都尝试扩大窗口。
- 获取当前字符：用char1 = s[right]获取right指针指向的字符。
- 检查字符是否在tMap中：通过if (tMap.has(char1))判断该字符是否是目标字符串t中需要的字符。
- 更新windowMap：如果是需要的字符，就更新windowMap中该字符的计数。
- 更新matched：当windowMap中该字符的计数和tMap中该字符的计数相等时，说明窗口中该字符的数量满足要求，matched加1。
- 右指针右移：执行right++，扩大窗口。
收缩窗口 (移动左指针)：
- while (matched === tMap.size)循环：当matched等于tMap.size时，表明当前窗口已经包含了t中所有字符且数量满足要求，此时尝试缩小窗口，看能否找到更小的覆盖子串。
- 更新最小子串信息：如果当前窗口的长度(right - left)小于minLen ，就更新minLen和start，记录下更小的覆盖子串。
- 获取左指针字符：用char2 = s[left]获取left指针指向的字符。
- 检查字符是否在tMap中：同样通过if (tMap.has(char2))判断。
- 更新windowMap：如果是需要的字符，将windowMap中该字符的数量减1。
- 更新matched：若窗口中该字符的数量小于tMap中该字符的数量，matched减1，表示不再满足覆盖要求。
- 左指针右移：执行left++，缩小窗口。
返回结果：
- 如果minLen仍然是Infinity，说明在遍历完整个s后，都没有找到满足条件的子串，返回空字符串""。
- 否则，使用s.substring(start, start + minLen)提取最小子串并返回。

3. 特别注意

Map的使用：正确运用Map的has、get和set方法是解题的关键。Map让字符计数和查找变得高效，方便判断窗口内字符的情况。
matched计数器的维护：matched计数器是算法的核心部分，它精确记录了窗口中已满足要求的字符种类数量。在更新windowMap和tMap时，要确保matched的增减与它们的状态同步。
窗口收缩的条件：只有当matched === tMap.size时，才可以收缩窗口；否则，需要继续扩展窗口，直到覆盖所有需要的字符。
更新最小子串的时机：只有在matched === tMap.size的情况下，才去检查并更新minLen和start 。
边界条件处理：要注意处理空字符串的情况，以及没有找到满足条件子串时的返回值。
重复字符的处理：算法能够正确处理t中包含重复字符的情况。windowMap和tMap存储了字符的精确数量，保证窗口中字符数量符合要求。