滑动窗口

0 Sliding Windows Basic 什么是滑动窗口？ 滑动窗口本质上是双指针的特殊形式：两个指针left和right同向移动，维护一个连续的区间[left, right)或[left, right] right负责扩张窗口纳入新元素，left负责收缩窗口排除不合法元素 $O(n^2) \Rightarrow O(n)$ 滑动窗口的两种类型： 类型 窗口大小 典型题 固定窗口 窗口大小 k 已知 字符串中所有字母异位词 可变窗口 窗口大小动态变化 无重复字符的最长子串 什么时候使用滑动窗口？关键词 前提是问题有单调性：窗口扩大时某个量单调变化(比如和变大、字符种类不减)；如果数组含负数导致"扩大窗口和不一定变大", 滑动窗口就失效了, 得换前缀和 + 哈希 连续子数组/子串 最长/最短的满足某条件的子串（不含重复元素/和大于等于target/至多k个不同元素） 包含/不包含某些字符的子串 固定窗口大小"或"可变窗口大小 模板：右指针负责扩展窗口，左指针负责收缩窗口，两者配合保证窗口始终满足某种约束 1def sliding_window(s): 2 window = {} # 维护窗口内的状态(计数、和等) 3 left = 0 4 ans = 0 5 for right in range(len(s)): 6 # 右端点元素进入窗口,更新状态 7 window[s[right]] = window.get(s[right], 0) + 1 8 9 # 当窗口不满足条件时,收缩左端点 10 while 窗口不合法: 11 window[s[left]] -= 1 12 left += 1 13 14 # 窗口合法,更新答案 15 ans = max(ans, right - left + 1) 16 return ans 1 无重复字符的最长子串 | Medium 题目：给定字符串 s，找出不含有重复字符的最长子串的长度。 ...