Python滑动窗口算法

"""
滑动窗口 — 高效处理连续子数组/子串的利器
固定窗口滑移求和；可变窗口用左右指针维护合法区间
"""


def fixed_window_sum(arr: list, k: int) -> list:
"""所有长度为 k 的子数组和，增量更新 O(n)"""
if len(arr) < k: return []
cur = sum(arr[:k])
res = [cur]
for i in range(k, len(arr)):
cur += arr[i] - arr[i - k]
res.append(cur)
return res


def length_of_longest_substring(s: str) -> int:
"""无重复字符的最长子串 (LeetCode 3)"""
used = {}
left = mx = 0
for r, ch in enumerate(s):
if ch in used and used[ch] >= left:
left = used[ch] + 1
used[ch] = r
mx = max(mx, r - left + 1)
return mx


def min_window(s: str, t: str) -> str:
"""最小覆盖子串 (LeetCode 76)"""
from collections import Counter
need = Counter(t)
miss = len(t)
left = 0
best = (float('inf'), 0)
for r, ch in enumerate(s):
if need[ch] > 0: miss -= 1
need[ch] -= 1
while miss == 0:
if r - left + 1 < best[0]:
best = (r - left + 1, left)
lc = s[left]
need[lc] += 1
if need[lc] > 0: miss += 1
left += 1
return s[best[1]:best[1] + best[0]] if best[0] != float('inf') else ""


def min_subarray_len(target: int, nums: list) -> int:
"""和 >= target 的最短子数组 (LeetCode 209)"""
left = cur = 0
best = float('inf')
for r, v in enumerate(nums):
cur += v
while cur >= target:
best = min(best, r - left + 1)
cur -= nums[left]; left += 1
return best if best != float('inf') else 0


def check_inclusion(s1: str, s2: str) -> bool:
"""s2 是否包含 s1 的排列 (LeetCode 567)"""
if len(s1) > len(s2): return False
from collections import Counter
need = Counter(s1); miss = len(s1)
for r, ch in enumerate(s2):
if need[ch] > 0: miss -= 1
need[ch] -= 1
l = r - len(s1)
if l >= 0:
need[s2[l]] += 1
if need[s2[l]] > 0: miss += 1
if miss == 0: return True
return False


def demo():
print(f"固定窗口 k=3 和: {fixed_window_sum([1,2,3,4,5,6], 3)}")
print(f"无重复最长子串 'abcabcbb': {length_of_longest_substring('abcabcbb')}")
print(f"最小覆盖: {min_window('ADOBECODEBANC', 'ABC')}")
print(f"和>=7 最短: {min_subarray_len(7, [2,3,1,2,4,3])}")
print(f"排列 'ab' in 'eidbaooo': {check_inclusion('ab', 'eidbaooo')}")


if __name__ == "__main__":
demo()