滑动窗口
解题思路
利用滑动窗口来解决该题；
初始化一个 hash 表来记录 t 中的字母，tLen 长度为 t 的长度 （维护 tLen 效率较高，维护两个 hash 表不断对比效率较低）；
当
tLen === 0说明窗口内存在 覆盖子串 ，先扩张窗口右边界找到 覆盖子串 ，再缩减窗口左边界找到 最小覆盖子串
- 当窗口右边界向右扩张，减去扩张进来的元素并且 tLen– ，根据窗口内元素维护 hash 表和 tLen；
- 当窗口左边界向右缩减，加上扩张进来的元素并且 tLen++ ，根据窗口内元素维护 hash 表和 tLen；
复杂度
-
时间复杂度：
O(N) -
空间复杂度：
O(1)
实现代码
var minWindow = function (s, t) {
const hash = new Array(128).fill(0); // 使用数组代替 Map，长度为 128 表示 ASCII 字符的个数
let left = 0;
let right = 0;
let tLen = t.length; // 维护 t 的长度，为 0 的时候表示当前字符串包含了 t
let res = ''; // 初始化 res
let minLen = Infinity; // 根据最小长度，更新 res
// 1. 初始化 t 中的字母个数，放到 hash 表中，未出现的字母个数为 0
for (const char of t) {
hash[char.charCodeAt(0)]++; // 将字符的 ASCII 值作为数组下标
}
while (right < s.length) {
// 2. 窗口向右扩张，更新 hash 表，出现的字母数量减 1，更新 tLen
if (hash[s.charCodeAt(right)] > 0) {
tLen--; // 当前字符在 t 中，更新 tLen
}
hash[s.charCodeAt(right)]--;
right++;
// 3. tLen === 0 说明窗口内的所有元素包含 t 的所有字母，窗口左侧开始收缩
while (tLen === 0) {
// 找到一个包含 t 的子串，更新 res
if (right - left < minLen) {
minLen = right - left;
res = s.slice(left, right);
}
// 窗口左侧开始收缩，要将收缩的元素放到 hash 表中，继续维护 tLen，等待下一次 窗口的匹配
hash[s.charCodeAt(left)]++;
if (hash[s.charCodeAt(left)] > 0) {
tLen++; // left 指向的字符在 t 中，更新 tLen
}
left++;
}
}
return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 3. 无重复字符的最长子串
上一篇
评论
