Python刷题模板——滑动窗口

滑动窗口算法框架

扩大窗口:寻找可行解

缩小窗口:找到最优解

def slidingWindows(s,t): # source, target
    need = collections.Counter(t) # 需要出现的次数
    windows = dict.fromkeys(need.keys(),0) # 窗口中出现的次数
    left = right = 0 # 左右指针表示窗口[left,right)
    valid = 0 # 表示窗口中满足need条件的字符个数
    while right < len(s):
        c = s[right] # 移入窗口的字符
        right += 1

        # 窗口内数据的更新
        if c in need:
            windows[c] += 1
            if windows[c] == need[c]:
                valid += 1

        print(letf,right) # debug输出位置

        while shrink: # 左窗口需要收缩 valid >= len(need)
            d = s[left] # 移出窗口的字符
            left += 1

            # 窗口内数据的更新 
            if d in need:
                if windows[d] == need[d]:
                    valid -= 1
                windows[d] -= 1

思考四个问题:

1、当移动 right 扩大窗口,即加入字符时,应该更新哪些数据?

2、什么条件下,窗口应该暂停扩大,开始移动 left 缩小窗口?

3、当移动 left 缩小窗口,即移出字符时,应该更新哪些数据?

4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新?

相关题目

76. 最小覆盖子串

567. 字符串的排列

438. 找到字符串中所有字母异位词

3. 无重复字符的最长子串

发表评论