LeetCode滑动窗口解题笔记：无重复字符子串与最小覆盖子串

"这篇刷题记录主要涉及了两个与字符串处理相关的 LeetCode 题目，分别是关于滑动窗口的最长无重复字符子串问题和寻找字符串的最小覆盖子串问题。" 首先，我们来看第一个题目，【3.无重复字符的最长子串】。这个问题的目标是找到字符串`s`中不包含重复字符的最长子串的长度。这里用到了滑动窗口的概念，滑动窗口是一种在数组或字符串中查找满足特定条件的子集的有效方法。在本题中，滑动窗口的左右边界分别由变量`left`和`right`表示，窗口内的字符通过一个大小为128的哈希表`tmp`进行存储，用来检查字符是否重复。 算法的基本步骤如下： 1. 初始化窗口左右边界`left`和`right`为0，以及当前无重复字符子串长度`cnt`和最大长度`res`为0。 2. 遍历字符串`s`，将每个字符添加到窗口内，同时更新哈希表`tmp`。 3. 如果当前字符在哈希表中未出现过，说明它是一个新的无重复字符，窗口大小增加1，同时更新最大长度`res`。 4. 如果当前字符在哈希表中已经出现过，就需要从窗口左边界开始收缩窗口，直到找到第一个可以移除的重复字符（哈希表计数归零），然后更新`left`和`cnt`。 5. 重复步骤2-4，直到遍历完整个字符串`s`。 6. 最后返回最大长度`res`作为结果。 接下来，我们看第二个题目，【76.最小覆盖子串】。这个题目要求在字符串`s`中找到涵盖字符串`t`所有字符的最短子串。需要注意的是，如果`t`中的某个字符重复，那么子串中对应的字符也必须至少出现相同的次数。 解决方法仍然是使用滑动窗口，但这次我们需要维护窗口中字符的计数，以确保窗口内包含所有目标字符。算法如下： 1. 初始化窗口左右边界`left`和`right`为0，以及窗口内字符计数哈希表`count`和目标字符计数哈希表`target`。 2. 初始化最小覆盖子串起始索引`start`为-1，最小长度`min_len`为无穷大。 3. 遍历字符串`s`，更新窗口内字符的计数，并比较与目标字符的计数。 4. 当窗口内包含了`t`的所有字符时，检查当前窗口长度是否小于`min_len`，如果是，则更新`min_len`和`start`。 5. 如果窗口内缺少某个目标字符，收缩窗口的左边界，直至找到缺失的字符并更新相关计数。 6. 重复步骤3-5，直到遍历完整个字符串`s`。 7. 返回子串`s[start : start + min_len]`作为结果。 这两个题目都是字符串处理的经典问题，它们都利用了滑动窗口的特性来有效地查找满足特定条件的子串，同时在解题过程中体现了哈希表的高效性。通过练习这类题目，可以提升对字符串处理和滑动窗口算法的理解。