1.1 定长滑动窗口
1.1.1 基础
定长滑窗套路 我总结成三步：入-更新-出。 
- 入：下标为 i 的元素进入窗口，更新相关统计量。如果 i<k−1 则重复第一步。
- 更新：更新答案。一般是更新最大值/最小值。
- 出：下标为 i−k+1 的元素离开窗口，更新相关统计量。 以上三步适用于所有定长滑窗题目。
提示
阿囧说：代码实操中，先滑到k个窗口大小，然后位于s[i+1-k]的字符（想象指针回退k个窗口大小）先出，如果还有新字符则再次进循环，入新字符
class Solution: def maxVowels(self, s: str, k: int) -> int: yuanYin = "aeiou" res = 0 temp = 0 for i, c in enumerate(s): if c in yuanYin: temp += 1 if i + 1 < k: continue res = max(res, temp) if s[i + 1 - k] in yuanYin: temp -= 1 return res时间复杂度：O(n)
空间复杂度：O(1)
class Solution: def findMaxAverage(self, nums: List[int], k: int) -> float: res, temp = float('-inf'), 0 for i, num in enumerate(nums): temp += num if i + 1 < k: continue res = max(temp, res) temp -= nums[i + 1 - k] res /= k return res时间复杂度：O(n)
空间复杂度：O(1)
class Solution: def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int: temp, res = 0, 0 for i, num in enumerate(arr): temp += num if i + 1 < k: continue if temp / k >= threshold: res += 1 temp -= arr[i + 1 - k] return res时间复杂度：O(n)
空间复杂度：O(1)
我的丑陋解法：class Solution: def getAverages(self, nums: List[int], k: int) -> List[int]: res = [] temp, start = 0, 0 n = len(nums) if n <= 2 * k: res = [-1] * n return res else: for _ in range(k): res.append(-1) for i in range(k): start += nums[i] for i, num in enumerate(nums): start += nums[i + k] if i < k: continue res.append(start // (2 * k + 1)) start -= nums[i - k] if i + k + 1 == n: for _ in range(k): res.append(-1) break return res时间复杂度：O(n)
空间复杂度：O(n)
tips：但其实i应该滑到窗口的末端而不是中间，代码会简便很多
class Solution: def getAverages(self, nums: List[int], k: int) -> List[int]: n = len(nums) res = [-1] * n temp = 0 for i, num in enumerate(nums): temp += num if i < 2 * k: continue res[i - k] = temp // (2 * k + 1) temp -= nums[i - 2 * k] return res时间复杂度：O(n)
空间复杂度：O(n)
class Solution: def minimumRecolors(self, blocks: str, k: int) -> int: black = 0 res = float('inf') for i, c in enumerate(blocks): if c == 'B': black += 1 if i + 1 < k: continue res = min(k - black, res) if blocks[i + 1 - k] == 'B': black -= 1 return res时间复杂度：O(n)
空间复杂度：O(1)
这题有点意思class Solution: def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int: cus1, cus2, temp = 0, 0, 0 for i, (c, g) in enumerate(zip(customers, grumpy)): # 计算不发动技能，有多少顾客满意 if g == 0: cus1 += c # temp记录生气导致不满意的顾客 else: temp += c if i + 1 < minutes: continue # 用滑动窗口判断能挽回的客户最大值 cus2 = max(cus2, temp) # 如果退出的窗口是生气的temp才减少 if grumpy[i + 1 - minutes] == 1: temp -= customers[i + 1 - minutes] return cus1 + cus2时间复杂度：O(n)
空间复杂度：O(1)
1461. 检查一个字符串是否包含所有长度为 K 的二进制子串
巧用集合和切片
class Solution: def hasAllCodes(self, s: str, k: int) -> bool: set1 = set() temp = '' for i, c in enumerate(s): temp += c if i + 1 < k: continue set1.add(temp) temp = temp[1:] if len(set1) == 2 ** k: return True else: return False时间复杂度：O(nk)
空间复杂度：O()
我的使用集合写法，O(k)，总的时间复杂度是 O((n-k)*k)，不是 O(n)。当 k=n/2 时算法的时间复杂度是 O(n^2)。在力扣通过运行花了7秒，夸张QAQ。class Solution: def maxSum(self, nums: List[int], m: int, k: int) -> int: temp_list = [] temp_sum = 0 res = 0 for i, num in enumerate(nums): temp_list.append(num) if i + 1 < k: continue if len(set(temp_list)) < m: temp_list = temp_list[1:] continue else: temp_sum = sum(temp_list) res = max(res, temp_sum) temp_list = temp_list[1:] return res时间复杂度：O(nk)
空间复杂度：O(k)
灵神的哈希表写法
class Solution: def maxSum(self, nums: List[int], m: int, k: int) -> int: ans = 0 s = sum(nums[:k - 1]) # 先统计 k-1 个数 cnt = Counter(nums[:k - 1]) for out, in_ in zip(nums, nums[k - 1:]): s += in_ # 再添加一个数就是 k 个数了 cnt[in_] += 1 if len(cnt) >= m: ans = max(ans, s) s -= out # 下一个子数组不包含 out，移出窗口 cnt[out] -= 1 if cnt[out] == 0: del cnt[out] return ans时间复杂度：O(n)
空间复杂度：O(k)
我的使用集合写法，力扣超时无法通过，时代的眼泪，以后这种类型的题改为哈希表写法了。class Solution: def maximumSubarraySum(self, nums: List[int], k: int) -> int: temp, res = 0, 0 for i, num in enumerate(nums): temp += num if i + 1 < k: continue if len(set(nums[i + 1 - k:i + 1])) == k: res = max(res, temp) temp -= nums[i + 1 - k] return res时间复杂度：O(nk)
空间复杂度：O(k)
哈希表yyds
class Solution: def maximumSubarraySum(self, nums: List[int], k: int) -> int: temp, res = sum(nums[:k - 1]), 0 cnt = Counter(nums[:k - 1]) for in_, out in zip(nums[k - 1:], nums): # 入 temp += in_ cnt[in_] += 1 # 更新 if len(cnt) == k: res = max(res, temp) # 出 temp -= out cnt[out] -= 1 if cnt[out] == 0: del cnt[out] return res时间复杂度：O(n)
空间复杂度：O(k)
这题很有点意思解法一：逆向思维：求剩下的牌点数最小之和，剩下的牌一定是连续的，可以视为滑动窗口
class Solution: def maxScore(self, cardPoints: List[int], k: int) -> int: n = len(cardPoints) m = n - k min_s = s = sum(cardPoints[:m]) for i in range(m, n): s += cardPoints[i] - cardPoints[i - m] min_s = min(min_s, s) return sum(cardPoints) - min_s时间复杂度：O(n)
空间复杂度：O(1)
解法二：可以把后k个元素和前k个元素组成一个新的列表
class Solution: def maxScore(self, cardPoints: List[int], k: int) -> int: res, temp = 0, 0 nums = cardPoints[-k:] + cardPoints[:k] for i, num in enumerate(nums): temp += num if i + 1 < k: continue res = max(res, temp) temp -= nums[i + 1 -k] return res时间复杂度：O(k)
空间复杂度：O(k)
同解法二，不使用列表存储，枚举所有情况取最大值
class Solution: def maxScore(self, cardPoints: List[int], k: int) -> int: res = temp = sum(cardPoints[:k]) for i in range(1, k + 1): temp += cardPoints[-i] - cardPoints[k - i] res = max(res, temp) return res时间复杂度：O(k)
空间复杂度：O(1)
拆不了一点，没看懂class Solution: def decrypt(self, code: List[int], k: int) -> List[int]: n = len(code) res = [0] * n r = k + 1 if k > 0 else n k = abs(k) temp = sum(code[r - k:r]) for i in range(n): res[i] = temp temp += code[(r) % n] - code[(r - k) % n] r += 1 return res时间复杂度：O(n)
空间复杂度：O(1)
汗流浃背了，使用词典的滑动窗口class Solution: def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int: dic = defaultdict(int) for i in range(len(s) - minSize + 1): # 因为这里是字符串，所以可以通过切片快速构造滑动窗口 temp = s[i: i + minSize] if len(set(temp)) <= maxLetters: dic[temp] += 1 return max(dic.values()) if dic else 0时间复杂度：O(n * m)，其中 n 是字符串 s 的长度, m 是minSize
空间复杂度：O(k)，其中 k 是字典中存储的不同子串的数量
dic = defaultdict(int)和dic = {}的区别： defaultdict(int) 会自动为新键分配默认值 0（因为 int() 的返回值是 0）。当你访问一个不存在的键时，不会引发 KeyError，而是返回 0。普通字典在访问不存在的键时，会抛出 KeyErrordefaultdict和Counter的区别：
- defaultdict：用于创建带有默认值的字典。可以指定默认值的类型（如 int, list, set 等）。 适用于需要管理键值对并且可能在访问时需要默认值的情况。
- Counter：特别设计用于计数对象的出现次数。它自动将新键的计数初始化为 0，并在每次增加时更新计数。适用于频率计数和统计
词典是一种基于哈希表的实现，Counter也是基于字典实现的，专注于计数
使用Counter的滑动窗口
class Solution: def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int: cnt = Counter() temp = '' for i, c in enumerate(s): temp += c if i + 1 < minSize: continue if len(set(temp)) <= maxLetters: cnt[temp] += 1 temp = temp[1:] return max(cnt.values()) if cnt else 0时间复杂度：O(n * m)，其中 n 是字符串 s 的长度, m 是minSize
空间复杂度：O(m)，其中 m 是minSize