一、滑动窗口算法(Sliding Window Algorithm),该算法通过使用特定大小的子列表,在遍历完整列表的同时进行特定的操作,以达到降低了循环的嵌套深度。
二、滑动窗口算法可以以解决数组/字符串的子元素问题,它可以将嵌套的循环问题,转换为单循环问题,降低事件复杂度。
待整理:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/yi-ge-mo-ban-miao-sha-10dao-zhong-deng-n-sb0x/ (题目解答参考:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/)
class Solution:
def problemName(self, s: str) -> int:
# Step 1: 定义需要维护的变量们 (对于滑动窗口类题目,这些变量通常是最小长度,最大长度,或者哈希表)
x, y = ..., ...
# Step 2: 定义窗口的首尾端 (start, end), 然后滑动窗口
start = 0
for end in range(len(s)):
# Step 3: 更新需要维护的变量, 有的变量需要一个if语句来维护 (比如最大最小长度)
x = new_x
if condition:
y = new_y
'''
------------- 下面是两种情况,读者请根据题意二选1 -------------
'''
# Step 4 - 情况1
# 如果题目的窗口长度固定:用一个if语句判断一下当前窗口长度是否达到了限定长度
# 如果达到了,窗口左指针前移一个单位,从而保证下一次右指针右移时,窗口长度保持不变,
# 左指针移动之前, 先更新Step 1定义的(部分或所有)维护变量
if 窗口长度达到了限定长度:
# 更新 (部分或所有) 维护变量
# 窗口左指针前移一个单位保证下一次右指针右移时窗口长度保持不变
# Step 4 - 情况2
# 如果题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
# 如果当前窗口不合法时, 用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
# 在左指针移动之前更新Step 1定义的(部分或所有)维护变量
while 不合法:
作者:eason734
链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/yi-ge-mo-ban-miao-sha-10dao-zhong-deng-n-sb0x/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。