Python算法训练序列

双指针与滑动窗口 · Unit 05

← Unit 04
3
LeetCode 3Longest Substring Without Repeating Characters

窗口先扩张，
违反约束时再从左侧修复。

相向双指针维护的是尚未排除的搜索区间；滑动窗口维护的是一个连续、当前合法的候选答案。右指针负责尝试加入新元素，左指针负责在条件被破坏时恢复合法性。

LeetCode #3 原题内容中文转述 · 示例、约束与提交签名

题目要求

给定字符串 s，找出其中不含重复字符的最长子串长度。子串必须由原字符串中的连续字符组成。

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: # 返回最长无重复连续子串长度

约束

  • 0 ≤ len(s) ≤ 50000
  • s 可以包含英文字母、数字、符号和空格。

示例

s = "abcabcbb"
输出：3
最长子串可以是"abc"
s = "bbbbb"
输出：1
最长子串为"b"
s = "pwwkew"
输出：3
最长子串可以是"wke"

概念提醒

子串必须连续。例如"pwwkew"中的"pwke"不是合法子串，因为它跳过了中间字符。

先连接上一单元：从“向中间排除”切换为“向右维护窗口”Unit 04 → Unit 05
#15：搜索区间逐渐缩小

固定锚点后，left 与 right 从两端向中间移动，用单调性排除不可能的组合。

→
#3：候选窗口动态平移

right 持续读入新字符；约束被破坏时，left 向右修复窗口。两个边界都只向右。

双指针没有消失，只是边界语义改变：#15 的区间表示“尚未排除的搜索空间”；#3 的区间表示“当前连续候选答案”。学习滑动窗口时，先问窗口保存什么状态、何时失效、由哪一端修复。
1. 区分子串
2. 体验重复枚举
3. 建立滑动窗口
4. 代码联动
5. 最短窗口迁移
演示字符串：s = "abcabcbb"等待操作
当前窗口 s[left:right+1]
a
窗口字符集合 chars
目前最佳答案
best = 1，substring = "a"

当前循环不变量

s[left:right+1]始终是不含重复字符的连续子串。

当前移动规则

right尝试加入新字符；若重复，则持续移除s[left]并右移left，直到窗口重新合法。

left0
right0
当前字符a
窗口长度1
best1
按起点重新扫描的重复工作

从每个起点重新向右扩展时，大量字符会被反复检查。例如起点0已经验证过"abc"，起点1又会重新验证"bca"。滑动窗口不会清空全部状态，而是只移除已经离开窗口的左端字符。

补全 LeetCode 提交代码显式收缩窗口版本
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
chars = set()
left =
best = 0
for right in range(len(s)):
while :
left += 1
best = max(best, )
return best
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: chars = set() left = 0 best = 0 for right in range(len(s)): while s[right] in chars: chars.remove(s[left]) left += 1 chars.add(s[right]) best = max(best, right - left + 1) return best
进阶写法：也可以使用 last_seen[ch] 记录字符最近位置，重复时直接执行 left = max(left, last_seen[ch] + 1)。本单元主动画采用set逐步收缩版本，因为它更清楚地展示“违反约束后如何恢复窗口合法性”。
代码—窗口—set联动轨迹：s="abcabcbb"
1class Solution:
2 def lengthOfLongestSubstring(self, s: str) -> int:
3 chars = set()
4 left = 0
5 best = 0
6 for right in range(len(s)):
7 while s[right] in chars:
8 chars.remove(s[left])
9 left += 1
10 chars.add(s[right])
11 best = max(best, right - left + 1)
12 return best
逐行播放，观察right遇到第二个a时，left如何收缩窗口。
完成代码联动后进入最短窗口迁移补全正确、查看答案或播放完整轨迹后解锁。

迁移题：LeetCode #209 长度最小的子数组

不再从带有 pass 的空白编辑器起步。先复用 #3 的“right 扩张、left 收缩、维护连续窗口”，再辨认最关键的变化：#3 在窗口非法时收缩，#209 在窗口已经满足条件时主动收缩，以逼近最短答案。

1. 对照最长窗口与最短窗口
2. 映射四个语义变化
3. 拼装并运行收缩时机

已经掌握：#3 最长无重复子串

窗口状态：chars 集合 right 加入：chars.add(s[right]) 收缩触发：新字符导致窗口非法 收缩动作：移除 s[left] 答案目标：合法后更新最大长度

准备迁移：#209 最短达标子数组

窗口状态：current_sum right 加入：current_sum += nums[right] 收缩触发：窗口和已经达到 target 收缩动作：减去 nums[left] 答案目标：收缩过程中更新最小长度
保持不变窗口必须连续；right 逐项扩张；left 只向右；窗口状态随元素进入和离开做局部更新。
需要替换集合改为窗口和；“修复非法”改为“在仍然合法时尽量缩短”；最大值改为最小值，并处理无解哨兵。
为什么正整数条件是迁移成立的关键？ 因为所有元素为正：right 扩张只会让窗口和增大，left 收缩只会让窗口和减小。当 current_sum < target 时，移动 left 不可能改善条件，只能继续扩张；当已经达标时，才有资格不断收缩寻找更短窗口。

先判断迁移幅度：下面哪句话最准确？

槽位 A｜窗口状态与“尚未找到答案”的哨兵怎样初始化？

槽位 B｜right 读入一个正整数时，怎样更新窗口状态？

槽位 C｜什么时候收缩，以及进入 while 后先做什么？

槽位 D｜遍历结束后如何区分“无解”和“找到最短长度”？

更新顺序不能颠倒：进入 while current_sum >= target 时，当前窗口仍是合法答案。必须先用它更新 best，再移除左端；否则可能把一个有效窗口删掉后才记录，直接漏解。
复用的窗口骨架left=0、right 单向扩张、while 内 left 单向收缩，以及进入/离开窗口时局部更新状态。
改变的合法性语义#3 的 while 用于恢复合法；#209 的 while 在窗口仍然达标时继续压缩，目标是逼近最短长度。
新增的答案哨兵最小值不能初始化为0，因此用 len(nums)+1 表示“尚未发现任何达标窗口”。

#3：最长合法窗口

chars = set()
left = 0
best = 0
for right in range(len(s)):
    while s[right] in chars:
        chars.remove(s[left])
        left += 1
    chars.add(s[right])
    best = max(best, right-left+1)
return best

#209：最短达标窗口

current_sum = 0
left = 0
best = len(nums) + 1
for right in range(len(nums)):
    current_sum += nums[right]
    while current_sum >= target:
        best = min(best, right-left+1)
        current_sum -= nums[left]
        left += 1
return 0 if best == len(nums)+1 else best
迁移运行轨迹0/0
可选挑战：脱离槽位，独立重写完整代码

这一步不阻碍主流程。编辑器保留了窗口骨架，你只需要补回窗口和、达标收缩、最短值更新和无解返回。

本单元形成的算法Skill

滑动窗口适合连续区间问题。right负责引入新元素，left负责在约束不满足或已经满足时调整左边界。核心不是背模板，而是明确：窗口表示什么、什么状态算合法、何时扩张、何时收缩、答案在收缩前还是收缩后更新。

LeetCode #3连续子串滑动窗口set维护状态最长合法窗口O(n)
#125镜像比较
#283读写指针
#167单调排除
#15锚点与去重
#3 当前动态滑动窗口