韶关市网站建设_网站建设公司_门户网站_seo优化

题目链接：

76. 最小覆盖子串 - 力扣（LeetCode）

思路：

1. 采用贪心算法，我们用 i 表示 当前 s 串中走到的位置，left 到 i 表示满足 s 串中含有 t 串 的 距离。

2. 我们需要维护 left 到 i 这块的 字符串，从中不断计算 迭代，如果 当前依旧满足，则 left 往左边缩进，直到不满足，我们继续贪心的往右边走，直到满足 覆盖 t 串的条件，然后继续 试探 left 的极限值在哪里

3. 用 map 这个容器来判断 是否 满足条件

代码：

/** * @param {string} s * @param {string} t * @return {string} */ var minWindow = function (s, t) { let res = "", mapS = new Map(), mapT = new Map(); function check() { for (let [key, value] of mapT) { if (!mapS.get(key)) return false if (value > mapS.get(key)) return false } return true } if (s.length < t.length) return "" for (let i = 0; i < t.length; i++) { mapT.set(t[i], mapT.get(t[i]) ? mapT.get(t[i]) + 1 : 1) } let left = 0; for (let i = 0; i < s.length; i++) { mapS.set(s[i], mapS.get(s[i]) ? mapS.get(s[i]) + 1 : 1) while (left <= i && check()) { if (res.length === 0 || (res.length > (i - left + 1))) res = s.substring(left, i + 1) // 向左缩进 mapS.set(s[left], mapS.get(s[left]) - 1) left++ } } return res; };