文章目录
- 一、滑动窗口是什么？
- 二、python实现滑动窗口
- 总结
一、滑动窗口是什么？
在数组上或者字符串上，用一个固定或可变长度的“窗口区间”，不断向右移动，每次只修改窗口左右边界、复用上一轮计算结果，避免重复遍历，把暴力双循环O（n^2）优化成O（n）。
二、python实现滑动窗口
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
s="pwwkew"count=0max_count=0look_up=set()#滑动窗口集合left=0#左边界foriinrange(len(s)):count+=1whiles[i]inlook_up:#窗口滑动的关键look_up.remove(s[left])#移除左边界的值left+=1#向右滑动count-=1ifcount>max_count:max_count=count look_up.add(s[i])print(max_count)总结
1.暴力双循环会重复计算大量区间和、统计量，时间复杂度为O(n^2)，相比于暴力双循环，滑 动窗口只增减刚进出窗口的元素，每个元素仅进窗口 1 次、出窗口 1 次，时间复杂度 O (n)。
2.滑动窗口只能处理连续区间，如果题目要选不连续元素（子集），不能用。
