Sliding Window 的核心是用两个边界left和right维护一个连续区间[left, right]right负责向右扩张窗口、把新元素加入窗口状态left负责在窗口不满足题目条件时向右收缩并同步移除左侧元素关键不是“移动两个指针”本身而是先定义清楚窗口里需要维护的state再把题意翻译成valid / invalid condition最后决定什么时候收缩和什么时候更新答案。常见state包括是否出现过用set重复问题字符或数字出现次数用dict/frequency map窗口和用sum/total窗口内 0 的数量用zero_count最高频字符用max_freq窗口最大/最小值可能需要 deque 等结构。Sliding Window 主要分两类Variable-size window和Fixed-size window。Variable-size window 的典型模板是for right扩张 → 更新 state →while window invalid移除left并left 1→ 在窗口合法时更新答案例如 Longest Substring Without Repeating Characters 的 invalid 条件是“出现重复字符”Minimum Size Subarray Sum 的 valid 条件是sum targetCharacter Replacement 的 valid 条件是window_size - max_freq k。Fixed-size window 则窗口长度必须保持为k典型逻辑是加入右端元素 → 如果window_size k就移除左端元素并移动left→ 当window_size k时检查答案例如 Permutation in String。判断 Sliding Window 题时先问四个问题1窗口表示什么连续区间2窗口状态要维护什么3什么时候 valid / invalid4答案在什么时候更新另外要始终同步 pointer 和 state例如left 1前通常要先从 set、dict、sum 中移除nums[left]窗口长度[l, r]是r - l 1。很多 Sliding Window 能从 O(n²) 优化到 O(n)原因是每个元素通常最多被right加入一次、被left移除一次而不是因为“用了两个指针”就天然是 O(n)。State Valid Invalid Shrink condition # Sliding Window 高频题答案总结## 1. #3 Longest Substring Without Repeating Characters**Type:** Variable-size Sliding Window**State:**用 set 记录当前窗口中的字符。**Valid Condition:**窗口内没有重复字符。**Invalid Condition:**s[r] 已经存在于 set 中。**Shrink:**不断删除 s[l]并 l 1直到 s[r] 不再重复。**Update Answer:**窗口重新合法后pythonbest max(best, r - l 1)seen set() l 0 for r in range(len(s)): while s[r] in seen: seen.remove(s[l]) l 1 seen.add(s[r]) best max(best, r - l 1)2. #424 Longest Repeating Character ReplacementType:Variable-size Sliding WindowState:count: frequency mapmax_freq: 当前窗口中最高字符频率Valid Condition:window_size - max_freq k即(r - l 1) - max_freq kInvalid Condition:(r - l 1) - max_freq kShrink:减少count[s[l]]然后l 1。Update Answer:窗口合法时best max(best, r - l 1)Core Idea:窗口长度减去最高频字符数量就是需要替换的字符数。3. #567 Permutation in StringType:Fixed-size Sliding WindowWindow Size:len(s1)State:need:s1的 frequency mapwindow: 当前窗口 frequency mapValid Condition:窗口长度等于len(s1)并且window needInvalid Condition:不是典型 variable window invalid。如果窗口长度大于len(s1)就必须缩小一次。Shrink:window[s2[l]] - 1l 1Update Answer:当window_size len(s1)时比较两个 frequency map。Core Idea:Permutation 不关心顺序只关心 frequency。4. #76 Minimum Window SubstringType:Variable-size Sliding WindowState:need:t中每个字符需要多少次window: 当前窗口 frequencyhave: 已经满足要求的字符种类数need_count: 总共需要满足的字符种类数Valid Condition:当前窗口已经覆盖t的全部字符及其 frequency。常见写法have need_countInvalid Condition:还没有完全覆盖t。Shrink:一旦窗口 valid就不断移动l尝试缩短窗口。Update Answer:窗口 valid 时先更新最短长度再 shrink。Core Idea:先扩张直到覆盖 t 再收缩直到不能继续满足5. #209 Minimum Size Subarray SumType:Variable-size Sliding WindowState:total表示当前窗口总和。Valid Condition:total targetInvalid Condition:total targetShrink:只要 valid就继续total - nums[l]l 1Update Answer:每次 valid 时best min(best, r - l 1)Core Pattern:for r in range(len(nums)): total nums[r] while total target: best min(best, r - l 1) total - nums[l] l 16. #239 Sliding Window MaximumType:Fixed-size Sliding WindowWindow Size:kState:Monotonic Deque保存候选最大值的 index。Valid / Invalid:这题不是典型 valid/invalid window。核心约束队头必须仍然在当前窗口内deque 中对应的值保持单调递减Shrink:如果队头 index 已经离开窗口deque[0] l就弹出。Update Answer:窗口长度达到k后answer.append(nums[deque[0]])Core Idea:不要每个窗口重新找最大值而是维护一个单调队列。7. #1004 Max Consecutive Ones IIIType:Variable-size Sliding WindowState:zero_countValid Condition:zero_count kInvalid Condition:zero_count kShrink:如果nums[l] 0zero_count - 1然后l 1Update Answer:best max(best, r - l 1)Core Idea:最多允许窗口里有k个 0。8. #1456 Maximum Number of Vowels in a Substring of Given LengthType:Fixed-size Sliding WindowWindow Size:kState:vowel_countValid Condition:窗口长度固定为k。Shrink:如果左边字符是元音vowel_count - 1然后l 1。Update Answer:best max(best, vowel_count)Core Idea:右边加入一个字符左边移出一个字符。9. #643 Maximum Average Subarray IType:Fixed-size Sliding WindowWindow Size:kState:window_sumValid Condition:窗口长度等于k。Shrink:窗口超过k时window_sum - nums[l]l 1Update Answer:维护最大window_sum。最后max_sum / kCore Idea:因为k固定最大平均值等价于最大窗口和。10. #438 Find All Anagrams in a StringType:Fixed-size Sliding WindowWindow Size:len(p)State:needwindowValid Condition:window need并且窗口长度等于len(p)。Shrink:窗口超过目标长度时移除左字符。Update Answer:如果 frequency 一样result.append(l)Core Idea:和 #567 Permutation in String 几乎相同只是一个返回 bool一个返回所有起始 index。11. #713 Subarray Product Less Than KType:Variable-size Sliding WindowState:productValid Condition:product kInvalid Condition:product kShrink:product // nums[l]l 1直到重新 valid。Update Answer:以r结尾的合法 subarray 数量r - l 1所以answer r - l 1Core Idea:不是求最长而是统计每个r对应多少个合法起点。12. #904 Fruit Into BasketsType:Variable-size Sliding WindowState:Frequency mapcountValid Condition:len(count) 2Invalid Condition:len(count) 2Shrink:减少count[fruits[l]]。如果变成 0删除这个 key。然后l 1Update Answer:best max(best, r - l 1)Core Idea:最多允许窗口中存在两种不同元素。13. #1493 Longest Subarray of 1s After Deleting One ElementType:Variable-size Sliding WindowState:zero_countValid Condition:zero_count 1Invalid Condition:zero_count 1Shrink:如果nums[l] 0zero_count - 1然后l 1Update Answer:best max(best, r - l)注意不是r - l 1因为题目要求必须删除一个元素。14. #2024 Maximize the Confusion of an ExamType:Variable-size Sliding WindowState:可以维护T_countF_count或者 frequency map。Valid Condition:如果想把窗口全部变成TF_count k如果想变成FT_count k也可以统一写成window_size - max_freq kInvalid Condition:window_size - max_freq kShrink:减少左字符 frequencyl 1。Update Answer:best max(best, r - l 1)Core Idea:和 #424 Character Replacement 本质一样。15. #1343 Number of Sub-arrays of Size K and Average ThresholdType:Fixed-size Sliding WindowWindow Size:kState:window_sumValid Condition:window_sum / k threshold更推荐window_sum threshold * k避免浮点运算。Shrink:窗口超过k时移除nums[l]。Update Answer:窗口长度为k且满足条件count 116. #1876 Substrings of Size Three with Distinct CharactersType:Fixed-size Sliding WindowWindow Size:3State:可以用 set 或 frequency map。Valid Condition:三个字符全部不同。例如len(set(s[l:r1])) 3Shrink:保持窗口大小为 3。Update Answer:合法时answer 117. #219 Contains Duplicate IIType:Fixed / Bounded Sliding WindowState:seen set()保存最近k个位置中的值。Valid Condition:如果nums[r] in seen说明存在两个相同元素index 距离 k。Shrink:窗口超过允许范围时seen.remove(nums[l])l 1Update Answer:发现重复立即return TrueCore Idea:Set 只保存最近k个元素。18. #992 Subarrays with K Different IntegersType:Variable-size Sliding Window Counting直接做 exactly K 比较困难。核心转换exactly(K) atMost(K) - atMost(K - 1)atMost(K)State:frequency map distinct_countValid Condition:distinct_count KInvalid Condition:distinct_count KShrink:减少nums[l]frequency。如果 frequency 变成 0distinct_count - 1然后l 1Count Answer:每个r对应r - l 1个合法 subarray。最终exactly_k atMost(k) - atMost(k - 1)Sliding Window 总体判断模板看到题目先回答1. Fixed-size 还是 Variable-size 2. Window state 是什么 3. Valid condition 是什么 4. Invalid condition 是什么 5. 什么时候 shrink 6. 什么时候 update answerState 选择速记只需要判断“出现过没有” → Set 需要知道字符/数字出现次数 → Dict / Frequency Map 需要当前窗口总和 → running sum 需要当前窗口乘积 → running product 需要窗口里 0 的数量 → zero_count 需要窗口里不同元素种类数 → frequency map distinct_count 需要最高频字符数量 → frequency map max_freq 需要窗口最大值 → monotonic deque 需要 exactly K distinct → atMost(K) - atMost(K-1)Variable-size 通用模板l 0for r in range(len(nums)): # 1. add nums[r] into window state while window_invalid: # 2. remove nums[l] from state l 1 # 3. update answerFixed-size 通用模板l 0for r in range(len(nums)): # add nums[r] if r - l 1 k: # remove nums[l] l 1 if r - l 1 k: # check / update answer一句话总记忆Sliding Window Right 扩张 维护 State 判断 Valid / Invalid Left 收缩 更新答案真正难点不是移动 pointer而是定义State Valid Condition Shrink Condition Answer Update Condition
Python coding sliding window
Sliding Window 的核心是用两个边界left和right维护一个连续区间[left, right]right负责向右扩张窗口、把新元素加入窗口状态left负责在窗口不满足题目条件时向右收缩并同步移除左侧元素关键不是“移动两个指针”本身而是先定义清楚窗口里需要维护的state再把题意翻译成valid / invalid condition最后决定什么时候收缩和什么时候更新答案。常见state包括是否出现过用set重复问题字符或数字出现次数用dict/frequency map窗口和用sum/total窗口内 0 的数量用zero_count最高频字符用max_freq窗口最大/最小值可能需要 deque 等结构。Sliding Window 主要分两类Variable-size window和Fixed-size window。Variable-size window 的典型模板是for right扩张 → 更新 state →while window invalid移除left并left 1→ 在窗口合法时更新答案例如 Longest Substring Without Repeating Characters 的 invalid 条件是“出现重复字符”Minimum Size Subarray Sum 的 valid 条件是sum targetCharacter Replacement 的 valid 条件是window_size - max_freq k。Fixed-size window 则窗口长度必须保持为k典型逻辑是加入右端元素 → 如果window_size k就移除左端元素并移动left→ 当window_size k时检查答案例如 Permutation in String。判断 Sliding Window 题时先问四个问题1窗口表示什么连续区间2窗口状态要维护什么3什么时候 valid / invalid4答案在什么时候更新另外要始终同步 pointer 和 state例如left 1前通常要先从 set、dict、sum 中移除nums[left]窗口长度[l, r]是r - l 1。很多 Sliding Window 能从 O(n²) 优化到 O(n)原因是每个元素通常最多被right加入一次、被left移除一次而不是因为“用了两个指针”就天然是 O(n)。State Valid Invalid Shrink condition # Sliding Window 高频题答案总结## 1. #3 Longest Substring Without Repeating Characters**Type:** Variable-size Sliding Window**State:**用 set 记录当前窗口中的字符。**Valid Condition:**窗口内没有重复字符。**Invalid Condition:**s[r] 已经存在于 set 中。**Shrink:**不断删除 s[l]并 l 1直到 s[r] 不再重复。**Update Answer:**窗口重新合法后pythonbest max(best, r - l 1)seen set() l 0 for r in range(len(s)): while s[r] in seen: seen.remove(s[l]) l 1 seen.add(s[r]) best max(best, r - l 1)2. #424 Longest Repeating Character ReplacementType:Variable-size Sliding WindowState:count: frequency mapmax_freq: 当前窗口中最高字符频率Valid Condition:window_size - max_freq k即(r - l 1) - max_freq kInvalid Condition:(r - l 1) - max_freq kShrink:减少count[s[l]]然后l 1。Update Answer:窗口合法时best max(best, r - l 1)Core Idea:窗口长度减去最高频字符数量就是需要替换的字符数。3. #567 Permutation in StringType:Fixed-size Sliding WindowWindow Size:len(s1)State:need:s1的 frequency mapwindow: 当前窗口 frequency mapValid Condition:窗口长度等于len(s1)并且window needInvalid Condition:不是典型 variable window invalid。如果窗口长度大于len(s1)就必须缩小一次。Shrink:window[s2[l]] - 1l 1Update Answer:当window_size len(s1)时比较两个 frequency map。Core Idea:Permutation 不关心顺序只关心 frequency。4. #76 Minimum Window SubstringType:Variable-size Sliding WindowState:need:t中每个字符需要多少次window: 当前窗口 frequencyhave: 已经满足要求的字符种类数need_count: 总共需要满足的字符种类数Valid Condition:当前窗口已经覆盖t的全部字符及其 frequency。常见写法have need_countInvalid Condition:还没有完全覆盖t。Shrink:一旦窗口 valid就不断移动l尝试缩短窗口。Update Answer:窗口 valid 时先更新最短长度再 shrink。Core Idea:先扩张直到覆盖 t 再收缩直到不能继续满足5. #209 Minimum Size Subarray SumType:Variable-size Sliding WindowState:total表示当前窗口总和。Valid Condition:total targetInvalid Condition:total targetShrink:只要 valid就继续total - nums[l]l 1Update Answer:每次 valid 时best min(best, r - l 1)Core Pattern:for r in range(len(nums)): total nums[r] while total target: best min(best, r - l 1) total - nums[l] l 16. #239 Sliding Window MaximumType:Fixed-size Sliding WindowWindow Size:kState:Monotonic Deque保存候选最大值的 index。Valid / Invalid:这题不是典型 valid/invalid window。核心约束队头必须仍然在当前窗口内deque 中对应的值保持单调递减Shrink:如果队头 index 已经离开窗口deque[0] l就弹出。Update Answer:窗口长度达到k后answer.append(nums[deque[0]])Core Idea:不要每个窗口重新找最大值而是维护一个单调队列。7. #1004 Max Consecutive Ones IIIType:Variable-size Sliding WindowState:zero_countValid Condition:zero_count kInvalid Condition:zero_count kShrink:如果nums[l] 0zero_count - 1然后l 1Update Answer:best max(best, r - l 1)Core Idea:最多允许窗口里有k个 0。8. #1456 Maximum Number of Vowels in a Substring of Given LengthType:Fixed-size Sliding WindowWindow Size:kState:vowel_countValid Condition:窗口长度固定为k。Shrink:如果左边字符是元音vowel_count - 1然后l 1。Update Answer:best max(best, vowel_count)Core Idea:右边加入一个字符左边移出一个字符。9. #643 Maximum Average Subarray IType:Fixed-size Sliding WindowWindow Size:kState:window_sumValid Condition:窗口长度等于k。Shrink:窗口超过k时window_sum - nums[l]l 1Update Answer:维护最大window_sum。最后max_sum / kCore Idea:因为k固定最大平均值等价于最大窗口和。10. #438 Find All Anagrams in a StringType:Fixed-size Sliding WindowWindow Size:len(p)State:needwindowValid Condition:window need并且窗口长度等于len(p)。Shrink:窗口超过目标长度时移除左字符。Update Answer:如果 frequency 一样result.append(l)Core Idea:和 #567 Permutation in String 几乎相同只是一个返回 bool一个返回所有起始 index。11. #713 Subarray Product Less Than KType:Variable-size Sliding WindowState:productValid Condition:product kInvalid Condition:product kShrink:product // nums[l]l 1直到重新 valid。Update Answer:以r结尾的合法 subarray 数量r - l 1所以answer r - l 1Core Idea:不是求最长而是统计每个r对应多少个合法起点。12. #904 Fruit Into BasketsType:Variable-size Sliding WindowState:Frequency mapcountValid Condition:len(count) 2Invalid Condition:len(count) 2Shrink:减少count[fruits[l]]。如果变成 0删除这个 key。然后l 1Update Answer:best max(best, r - l 1)Core Idea:最多允许窗口中存在两种不同元素。13. #1493 Longest Subarray of 1s After Deleting One ElementType:Variable-size Sliding WindowState:zero_countValid Condition:zero_count 1Invalid Condition:zero_count 1Shrink:如果nums[l] 0zero_count - 1然后l 1Update Answer:best max(best, r - l)注意不是r - l 1因为题目要求必须删除一个元素。14. #2024 Maximize the Confusion of an ExamType:Variable-size Sliding WindowState:可以维护T_countF_count或者 frequency map。Valid Condition:如果想把窗口全部变成TF_count k如果想变成FT_count k也可以统一写成window_size - max_freq kInvalid Condition:window_size - max_freq kShrink:减少左字符 frequencyl 1。Update Answer:best max(best, r - l 1)Core Idea:和 #424 Character Replacement 本质一样。15. #1343 Number of Sub-arrays of Size K and Average ThresholdType:Fixed-size Sliding WindowWindow Size:kState:window_sumValid Condition:window_sum / k threshold更推荐window_sum threshold * k避免浮点运算。Shrink:窗口超过k时移除nums[l]。Update Answer:窗口长度为k且满足条件count 116. #1876 Substrings of Size Three with Distinct CharactersType:Fixed-size Sliding WindowWindow Size:3State:可以用 set 或 frequency map。Valid Condition:三个字符全部不同。例如len(set(s[l:r1])) 3Shrink:保持窗口大小为 3。Update Answer:合法时answer 117. #219 Contains Duplicate IIType:Fixed / Bounded Sliding WindowState:seen set()保存最近k个位置中的值。Valid Condition:如果nums[r] in seen说明存在两个相同元素index 距离 k。Shrink:窗口超过允许范围时seen.remove(nums[l])l 1Update Answer:发现重复立即return TrueCore Idea:Set 只保存最近k个元素。18. #992 Subarrays with K Different IntegersType:Variable-size Sliding Window Counting直接做 exactly K 比较困难。核心转换exactly(K) atMost(K) - atMost(K - 1)atMost(K)State:frequency map distinct_countValid Condition:distinct_count KInvalid Condition:distinct_count KShrink:减少nums[l]frequency。如果 frequency 变成 0distinct_count - 1然后l 1Count Answer:每个r对应r - l 1个合法 subarray。最终exactly_k atMost(k) - atMost(k - 1)Sliding Window 总体判断模板看到题目先回答1. Fixed-size 还是 Variable-size 2. Window state 是什么 3. Valid condition 是什么 4. Invalid condition 是什么 5. 什么时候 shrink 6. 什么时候 update answerState 选择速记只需要判断“出现过没有” → Set 需要知道字符/数字出现次数 → Dict / Frequency Map 需要当前窗口总和 → running sum 需要当前窗口乘积 → running product 需要窗口里 0 的数量 → zero_count 需要窗口里不同元素种类数 → frequency map distinct_count 需要最高频字符数量 → frequency map max_freq 需要窗口最大值 → monotonic deque 需要 exactly K distinct → atMost(K) - atMost(K-1)Variable-size 通用模板l 0for r in range(len(nums)): # 1. add nums[r] into window state while window_invalid: # 2. remove nums[l] from state l 1 # 3. update answerFixed-size 通用模板l 0for r in range(len(nums)): # add nums[r] if r - l 1 k: # remove nums[l] l 1 if r - l 1 k: # check / update answer一句话总记忆Sliding Window Right 扩张 维护 State 判断 Valid / Invalid Left 收缩 更新答案真正难点不是移动 pointer而是定义State Valid Condition Shrink Condition Answer Update Condition
