网站页脚版权信息,父亲节网页制作素材,爱站网为什么不能用了,wordpress修改成中文滑动窗口详解#xff1a;解决无重复字符的最长子串问题
在算法面试中#xff0c;“无重复字符的最长子串”问题是一个经典题目#xff0c;不仅考察基础数据结构的运用#xff0c;还能够反映你的逻辑思维能力。而在解决这个问题时#xff0c;滑动窗口#xff08;Sliding …滑动窗口详解解决无重复字符的最长子串问题
在算法面试中“无重复字符的最长子串”问题是一个经典题目不仅考察基础数据结构的运用还能够反映你的逻辑思维能力。而在解决这个问题时滑动窗口Sliding Window算法可以说是绝对的明星。本篇文章将带你深入理解滑动窗口的原理并通过代码和案例一步步解析如何应用它解决该问题。 问题描述
给定一个字符串 s请你找出其中不含有重复字符的最长子串的长度。
例如
输入s abcabcbb输出3因为最长子串是 “abc”。输入s bbbbb输出1因为最长子串是 “b”。输入s pwwkew输出3因为最长子串是 “wke”。
乍一看这个问题可能让人觉得需要两重循环暴力解决。但我们如何优化到线性时间复杂度呢这时滑动窗口大显身手。 滑动窗口的原理
滑动窗口是一种双指针技巧通常用来解决子数组或子串相关问题。它的核心思想是
用两个指针标记窗口的左右边界。动态调整窗口大小以满足问题条件。在移动窗口的过程中记录答案。
滑动窗口的优势在于它可以避免不必要的重复计算从而优化时间复杂度。 滑动窗口解法详解
我们来看具体的实现
# 主函数寻找无重复字符的最长子串
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:right1]}当前长度{current_length})return max_length代码详解 初始化 char_set 是一个集合用来存储当前窗口中的字符。left 是滑动窗口的左边界。max_length 用来记录当前最长的无重复子串长度。 遍历字符串 用 right 指针扩展窗口。如果 s[right] 在 char_set 中则表示出现了重复字符需要通过移动左指针 left 来缩小窗口直到重复字符被移除。 更新答案 每次调整窗口后计算当前窗口的长度并更新 max_length。 示例运行
我们以 s abcabcbb 为例逐步运行代码
初始状态窗口为空left 0max_length 0。遍历字符串 右指针移动到 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。 常见扩展问题
找出最长子串本身 如果不仅要返回长度还要返回子串本身可以在代码中记录窗口的起始位置。
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]滑动窗口在其他场景中的应用 滑动窗口求和问题固定窗口大小求最大子数组和。双指针应用于字符串匹配问题如查找最短覆盖子串。 总结
通过滑动窗口我们可以优雅地解决“无重复字符的最长子串”问题。这种算法思想不仅高效还能迁移到很多其他问题中。作为算法学习者理解并掌握滑动窗口是进阶的必经之路。
如果你对滑动窗口有任何问题或者想探索更多类似问题的解决方法欢迎在评论区与我交流
