Python算法训练序列

双指针与滑动窗口 · Unit 05

← Unit 04

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"不是合法子串，因为它跳过了中间字符。

1. 区分子串

2. 体验重复枚举

3. 建立滑动窗口

4. 代码联动

5. 最短窗口迁移

演示字符串：s = "abcabcbb"等待操作

当前窗口 s[left:right+1]

窗口字符集合 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"

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

逐行播放，观察right遇到第二个a时，left如何收缩窗口。

完成代码联动后进入最短窗口迁移补全正确、查看答案或播放完整轨迹后解锁。

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

给定正整数数组和目标值 target，寻找和大于等于target的最短连续子数组。right负责扩大窗口和；当窗口已经满足条件时，left持续收缩并更新最短长度。

本单元形成的算法Skill

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

LeetCode #3连续子串滑动窗口set维护状态最长合法窗口O(n)

#125镜像比较

#283读写指针

#167单调排除

#15锚点与去重

#3 当前动态滑动窗口