滑动窗口详解：解决无重复字符的最长子串问题

滑动窗口详解：解决无重复字符的最长子串问题

在算法面试中，“无重复字符的最长子串”问题是一个经典题目，不仅考察基础数据结构的运用，还能够反映你的逻辑思维能力。而在解决这个问题时，滑动窗口（Sliding Window）算法可以说是绝对的明星。本篇文章将带你深入理解滑动窗口的原理，并通过代码和案例一步步解析如何应用它解决该问题。

---

问题描述

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

例如：

• 输入：s = "abcabcbb"，输出：3，因为最长子串是 “abc”。
• 输入：s = "bbbbb"，输出：1，因为最长子串是 “b”。
• 输入：s = "pwwkew"，输出：3，因为最长子串是 “wke”。

乍一看，这个问题可能让人觉得需要两重循环暴力解决。但我们如何优化到线性时间复杂度呢？这时，滑动窗口大显身手。

---

滑动窗口的原理

滑动窗口是一种双指针技巧，通常用来解决子数组或子串相关问题。它的核心思想是：

1. 用两个指针标记窗口的左右边界。
2. 动态调整窗口大小以满足问题条件。
3. 在移动窗口的过程中记录答案。

滑动窗口的优势在于，它可以避免不必要的重复计算，从而优化时间复杂度。

---

滑动窗口解法详解

我们来看具体的实现：

# 主函数：寻找无重复字符的最长子串
def length_of_longest_substring(s: str) -> int:# 初始化变量char_set = set()  # 用于存储窗口内的字符left = 0          # 左指针max_length = 0    # 记录最大子串长度# 遍历字符串for right in range(len(s)):# 当字符重复时，缩小窗口while s[right] in char_set:print(f"重复字符：{s[right]}，移除左侧字符：{s[left]}")char_set.remove(s[left])left += 1# 将当前字符加入窗口char_set.add(s[right])# 更新最大长度current_length = right - left + 1max_length = max(max_length, current_length)print(f"窗口：{s[left:right+1]}，当前长度：{current_length}")return max_length

---

代码详解

1. 初始化：

   • char_set 是一个集合，用来存储当前窗口中的字符。
   • left 是滑动窗口的左边界。
   • max_length 用来记录当前最长的无重复子串长度。

2. 遍历字符串：

   • 用 right 指针扩展窗口。
   • 如果 s[right] 在 char_set 中，则表示出现了重复字符，需要通过移动左指针 left 来缩小窗口，直到重复字符被移除。

3. 更新答案：

   • 每次调整窗口后，计算当前窗口的长度，并更新 max_length。

---

示例运行

我们以 s = "abcabcbb" 为例，逐步运行代码：

1. 初始状态：窗口为空，left = 0，max_length = 0。
2. 遍历字符串：
   • 右指针移动到 0：窗口为 “a”，max_length = 1。
   • 右指针移动到 1：窗口为 “ab”，max_length = 2。
   • 右指针移动到 2：窗口为 “abc”，max_length = 3。
   • 右指针移动到 3：字符 “a” 重复，移除左侧的 “a”，窗口为 “bca”。
   • ……
   • 最终输出 max_length = 3。

---

时间复杂度分析

• 时间复杂度： 每个字符最多被左指针和右指针访问一次，时间复杂度为 O(n)。
• 空间复杂度： 需要一个集合存储窗口内的字符，空间复杂度为 O(k)，其中 k 是字符集的大小（对于英文字符，k 最多为 26）。

---

常见扩展问题

1. 找出最长子串本身：
   如果不仅要返回长度，还要返回子串本身，可以在代码中记录窗口的起始位置。

def longest_substring(s: str) -> str:char_set = set()left = 0max_length = 0start = 0for right in range(len(s)):while s[right] in char_set:char_set.remove(s[left])left += 1char_set.add(s[right])if right - left + 1 > max_length:max_length = right - left + 1start = leftreturn s[start:start + max_length]

2. 滑动窗口在其他场景中的应用：
   • 滑动窗口求和问题：固定窗口大小，求最大子数组和。
   • 双指针应用于字符串匹配问题，如查找最短覆盖子串。

---

总结

通过滑动窗口，我们可以优雅地解决“无重复字符的最长子串”问题。这种算法思想不仅高效，还能迁移到很多其他问题中。作为算法学习者，理解并掌握滑动窗口是进阶的必经之路。

如果你对滑动窗口有任何问题，或者想探索更多类似问题的解决方法，欢迎在评论区与我交流！