LeetCode 76 最小覆盖子串｜JS 滑动窗口标准解法（逐行精讲）

大家好，这篇文章用来记录LeetCode 76 最小覆盖子串的 JS 标准解法，这道题是滑动窗口的经典必做题，面试频率极高。

我会直接给出可 AC 代码，并逐行详细解释，方便自己复习也分享给大家。

题目简介

给两个字符串s和t，找出s中包含t所有字符的最短子串。
如果没有，返回空字符串""。

完整可提交代码

varminWindow=function(s,t){constneed={};constwindow={};letvalid=0;letleft=0,right=0;letstart=0,len=Infinity;// 统计 t 中每个字符需要的数量for(constcoft){need[c]=(need[c]||0)+1;}// 需要凑齐的字符种类数constneedSize=Object.keys(need).length;// 右指针遍历整个字符串while(right<s.length){constc=s[right];right++;// 如果当前字符是我们需要的if(need[c]){window[c]=(window[c]||0)+1;// 某一类字符数量达标，valid+1if(window[c]===need[c]){valid++;}}// 当窗口已经满足所有条件，开始收缩左侧while(valid===needSize){// 更新最小窗口if(right-left<len){start=left;len=right-left;}// 准备移除左指针字符constd=s[left];left++;// 如果是需要的字符，判断是否会破坏 validif(need[d]){if(window[d]===need[d]){valid--;}window[d]--;}}}// 没有找到返回空，否则返回截取的子串returnlen===Infinity?"":s.slice(start,start+len);};

逐行详细解析

1. 变量定义

constneed={};// 记录 t 中每个字符需要多少个constwindow={};// 记录当前窗口里每个字符有多少个letvalid=0;// 记录已经“数量达标”的字符种类数letleft=0,right=0;// 滑动窗口双指针letstart=0,len=Infinity;// 记录最终最短子串的起点和长度

• need：我们要找的字符目标数量
• window：当前窗口内的字符数量
• valid：核心判断条件，表示有多少种字符已经满足数量要求
• left/right：窗口左、右边界
• start/len：保存最优解，避免反复截取字符串

2. 统计目标字符

for(constcoft){need[c]=(need[c]||0)+1;}constneedSize=Object.keys(need).length;

• 遍历t，统计每个字符需要多少个
• needSize：一共需要凑齐多少种字符

3. 右指针扩大窗口

while(right<s.length){constc=s[right];right++;if(need[c]){window[c]=(window[c]||0)+1;if(window[c]===need[c]){valid++;}}

• 右指针一直往右走，扩大窗口
• 遇到需要的字符，就加入window计数
• 当某字符数量刚好达标时，valid += 1

4. 左指针收缩窗口（核心）

while(valid===needSize){// 更新最小窗口if(right-left<len){start=left;len=right-left;}constd=s[left];left++;if(need[d]){if(window[d]===need[d]){valid--;}window[d]--;}}

• 当valid === needSize，说明当前窗口已经包含了 t 所有字符
• 这时尽可能缩小窗口，寻找更短的子串
• 每次移动左指针前：
  • 先更新最小窗口记录
  • 再把左边字符移出窗口
  • 如果移出后导致某字符不满足数量，valid--，退出循环

5. 返回结果

returnlen===Infinity?"":s.slice(start,start+len);

• 如果len还是无穷大，说明没找到，返回空串
• 否则返回记录的最短子串

核心思想总结

这道题的核心就是滑动窗口 + 哈希计数：

1. 用右指针扩大窗口，直到满足条件
2. 用左指针收缩窗口，直到不满足条件
3. 全程记录最小窗口
4. 用valid精准判断窗口是否合法

这套模板可以通杀绝大多数子串滑动窗口题，非常实用。

测试用例

console.log(minWindow("ADOBECODEBANC","ABC"));// "BANC"console.log(minWindow("a","a"));// "a"console.log(minWindow("a","aa"));// ""