算法可视化

窗口扩张与收缩

看右指针如何扩张窗口，以及左指针在字符重复时如何收缩窗口。

s = "abcabcbb"

执行轨迹

    题目

    给定一个字符串，求不含重复字符的最长子串长度。

    题目分析

    这题最核心的不是枚举所有子串，而是维护一个始终“合法”的窗口。

    所谓合法，就是窗口内没有重复字符。只要这个条件被破坏，就移动左边界把窗口收缩回来。

    方法一：直觉解法

    最直觉的做法是枚举所有子串，再判断是否有重复字符。这个思路容易想到，但复杂度会比较差。

    方法二：优化思路

    滑动窗口的关键动作是：

    • 右指针不断向右扩张
    • 一旦出现重复字符，左指针向右收缩
    • 每次窗口合法时更新答案

    一般会配一个哈希表来记录字符出现次数。

    Go 实现

     1func lengthOfLongestSubstring(s string) int {
 2    counter := make(map[byte]int)
 3    left, ans := 0, 0
 4
 5    for right := 0; right < len(s); right++ {
 6        counter[s[right]]++
 7        for counter[s[right]] > 1 {
 8            counter[s[left]]--
 9            left++
10        }
11        if width := right - left + 1; width > ans {
12            ans = width
13        }
14    }
15
16    return ans
17}

    复杂度分析

    • 时间复杂度：O(n)
    • 空间复杂度：O(k)，k 为字符集大小

    易错点

    • 更新答案要放在窗口已经恢复合法之后
    • 左指针不是机械右移，而是要在“重复被消除”之前持续移动

    我的复盘

    滑动窗口看起来像技巧题，但本质上是在维护一个动态约束区间。把“窗口合法条件”想清楚，这类题就会稳定很多。