python滑动窗口的实现

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