基础算法题总结5--滑动窗口

LeetCode 中相关的题目：

题目详细描述

无重复字符的最长子串：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        occ = set() ## 哈希集合，记录每个字符是否出现过
        rk,ans = -1,0 ## rk表示右指针
        n = len(s)
        for i in range(n):
            if i != 0:
                occ.remove(s[i-1]) ## 左指针向右移动一位，则将哈希集合中元素去除
            ## 不断移动右指针，判断右指针元素是否出现过，直到到达边界或者元素已存在
            while rk+1<n and s[rk+1] not in occ:
                occ.add(s[rk+1])
                rk += 1
            ## 当前获取的长度如果比之前保存的长则更新结果
            if rk-i+1 > ans:
                ans = rk-i+1
        return ans

最小覆盖子串：

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        n,m = len(s),len(t)
        if n < m: return ""

need = collections.defaultdict(int) ## 初始化字典，哈希表
        for c in t:
            need[c] += 1
        need_cnt = m
        res = [0,n] ## res是用来记录起点终点，初始化为[0,n]

left = 0 ## 左指针
        for right,c in enumerate(s): ## 增加右边界使得滑动窗口包含t
            if need[c] > 0:
                need_cnt -= 1
            need[c] -= 1
            ## 1、找到右指针，目前字符串中已经包含了t中的所有的值
            if need_cnt == 0:
                ## 2、开始收缩左指针，将多余的不在t中的元素去掉
                while True:
                    if need[s[left]] == 0: ## 当再去掉就不全包含t了，到达边界条件
                        break
                    need[s[left]] += 1
                    left += 1  ## 左指针右移
                ## 当找到最小长度的起点终点，更新res
                if right - left < res[1] - res[0]:
                    res = [left,right]
                ## 3、已经更新结果，然后将left向右移动一位，开始下一次循环,寻找新的满足条件的滑动窗口
                need[s[left]] += 1
                need_cnt += 1 ## 此时移除的一定是所需的元素，所以需要增加1
                left += 1
        ## 如果res没有更新，就返回"",否则就返回更新的结果
        return s[res[0]:res[1]+1] if res != [0,n] else ""