大家好，我是速冻鱼🐟，一条水系前端💦，喜欢花里胡哨💐，持续沙雕🌲，是隔壁寒草🌿的好兄弟，刚开始写文章。 如果喜欢我的文章，可以关注➕点赞，为我注入能量，与我一同成长吧～
题目🦀
- 76. 最小覆盖子串难度
困难给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串""。注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
- 示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 复制代码
- 示例 2：
输入：s = "a", t = "a" 输出："a" 复制代码
- 示例 3:
输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。 复制代码
- 提示：
1 <= s.length, t.length <= 105s和t由英文字母组成
解题思路🌵
- 先找出所有包含T的子串
- 找出长度最小那个子串，返回即可
- 用双指针维护一个滑动窗口，用来枚举出所有的子串。
- 不断移动右指针，找到包含T的子串，移动左指针，尽量减少包含T的子串的长度。
源码🔥
/** * @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 c of t){ need.set(c,need.has(c)?need.get(c)+1:1); } let needType=need.size; let res=''; while(r<s.length){ const c=s[r]; if(need.has(c)){ need.set(c,need.get(c)-1) if(need.get(c)===0)needType-=1; } while(needType===0){ const newRes =s.substring(l,r+1); if(!res||newRes.length<res.length)res=newRes; const c2=s[l]; if(need.has(c2)){ need.set(c2,need.get(c2)+1); if(need.get(c2)===1)needType+=1; } l+=1; } r+=1; } return res; }; 复制代码
时间复杂度:O(m+n)，m是t的长度，n是s的长度。
空间复杂度:O(m)
结束语🌞
那么鱼鱼的LeetCode算法篇的76-最小覆盖子串就结束了，虽然前端对算法要求没有后端高，但是算法是编程基础，程序=数据结构➕算法，所以算法这个东西没有捷径，只能多写多练，多总结，文章的目的其实很简单，就是督促自己去完成算法练习并总结和输出，菜不菜不重要，但是热爱🔥，喜欢大家能够喜欢我的短文，也希望通过文章认识更多志同道合的朋友，如果你也喜欢折腾，欢迎加我好友，一起沙雕，一起进步。
