滑动窗口与螺旋矩阵算法详解与实战

1. 算法训练营第二天内容概览

今天我们要啃两块硬骨头——滑动窗口和螺旋矩阵。这两个算法技巧在笔试面试中的出场率绝对能排进前五，特别是滑动窗口，几乎是大厂必考题型。记得我第一次参加算法面试时，面试官连续出了三道滑动窗口变种题，当时真是被"窗口"卡得死死的。

滑动窗口本质上是一种优化暴力解法的技巧，它通过维护一个动态变化的窗口来避免重复计算。而螺旋矩阵则考验我们对二维数组索引的掌控能力，这类题目往往代码量不大，但边界条件特别容易出错。接下来我会用4道经典题目带大家掌握这两个算法的核心套路。

2. 滑动窗口算法深度解析

2.1 算法原理与适用场景

滑动窗口（Sliding Window）本质上是一种双指针技巧的变种，特别适合解决数组/字符串的子区间问题。它的核心思想是维护一个窗口，通过调整窗口的左右边界来高效地遍历所有可能的子区间。

适用滑动窗口的问题通常有这些特征：

1. 问题涉及数组/字符串的连续子序列
2. 要求计算满足某些条件的最长子串/最短子数组等
3. 暴力解法的时间复杂度通常在O(n²)级别

关键理解：滑动窗口通过消除重复计算将时间复杂度优化到O(n)。比如在字符串"abcabcbb"中找最长无重复子串，暴力法需要检查所有O(n²)个子串，而滑动窗口只需遍历一次。

2.2 基础模板与实现要点

所有滑动窗口问题都遵循这个基本框架：

python复制def slidingWindow(s: str):
    left = 0
    window = {}  # 用于记录窗口内字符出现次数
    res = 0      # 存储结果
    
    for right in range(len(s)):
        # 右指针移动，扩大窗口
        window[s[right]] = window.get(s[right], 0) + 1
        
        # 当窗口不满足条件时，收缩左边界
        while window needs shrink:
            # 更新结果（根据具体问题）
            res = update(res, window)
            
            # 左指针移动，缩小窗口
            window[s[left]] -= 1
            if window[s[left]] == 0:
                del window[s[left]]
            left += 1
    
    return res

实现时的三个关键点：

1. 窗口数据结构选择：通常用哈希表记录字符频率，有时只需维护一个计数器
2. 窗口收缩条件：这是算法的核心逻辑，决定何时移动左指针
3. 结果更新时机：可能在窗口收缩前、收缩中或收缩后更新

2.3 经典例题实战：无重复字符的最长子串

LeetCode第3题是滑动窗口的入门必做题：

题目：给定一个字符串s，找出其中不含有重复字符的最长子串的长度。

示例：
输入: s = "abcabcbb"
输出: 3 ("abc")

解法分析：

python复制def lengthOfLongestSubstring(s: str) -> int:
    left = 0
    max_le