Loading... ## 解题模板 什么是滑动窗口? 其实就是一个队列, 初始这个队列(窗口)包含的元素满足题目要求,但是当再进入新的元素时,队列此时这不满足要求。所以,我们要移动这个队列! 如何移动? 我们只要把队列的左边的元素移出就行了(可能需要移动不止一次),直到满足题目要求! 一直维持这样的队列,找出队列出现最长的长度时候,求出解! 链接:[原文地址](https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/3982/hua-dong-chuang-kou-by-powcai/) ## 相关题目 ### 示例1: 题目描述: [无重复字符的最长子串]() * 给定一个字符串 `s` ,请你找出其中不含有重复字符的 ** 最长子串 ** 的长度。 * LeetCode原文: [链接](https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/) 解法思路: * F1,直观但低效: 在每个位置处开始, 分别遍历之后的部分知道出现重复, 时间复杂度接近$O(n^2)$ * 简单优化一些, 也没有本质不同 * F2, 滑动窗口: 维护目标窗口, 右侧新增, 左侧不断移除元素, 使得新队列满足条件(无重复), 同时记录新队列长度, 整体时间复杂度为$O(n)$ 实现代码: <div class="tab-container post_tab box-shadow-wrap-lg"> <ul class="nav no-padder b-b scroll-hide" role="tablist"> <li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" aria-controls='tabs-d1cf8bc1ed194f140c859ecd8e8364c6560' role="tab" data-target='#tabs-d1cf8bc1ed194f140c859ecd8e8364c6560'>F2</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" aria-controls='tabs-c37c26329169b4c8c6149fd4f6946ece1001' role="tab" data-target='#tabs-c37c26329169b4c8c6149fd4f6946ece1001'>F1</a></li> </ul> <div class="tab-content no-border"> <div role="tabpanel" id='tabs-d1cf8bc1ed194f140c859ecd8e8364c6560' class="tab-pane fade active in"> ```python # 滑动窗口 class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if s is None: return 0 max_len = 0 lookup = dict() left = 0 index = 0 while index < len(s): if s[index] not in lookup: # 记录队列清单, 以及所处位置索引 lookup[s[index]] = index cur_len = len(lookup) if cur_len > max_len: max_len = cur_len else: # 不断移除队列左侧元素, 直到与右侧重复的位置停止 start = left end = lookup[s[index]] for i in range(start, end+1): lookup.pop(s[i]) # 更新左侧开始位置 left = end + 1 continue index += 1 return max_len ``` </div><div role="tabpanel" id='tabs-c37c26329169b4c8c6149fd4f6946ece1001' class="tab-pane fade "> ```python # 直观但低效 class Solution: def lengthOfLongestSubstring(self, s: str) -> int: max_len = 0 # 第一层遍历: fs: first start # for idx_fs in range(len(s)): idx_fs = 0 while idx_fs < len(s): hashtable = {} # 第二层遍历: ss: sencond start for idx_ss in range(idx_fs, len(s)): if s[idx_ss] not in hashtable: hashtable[s[idx_ss]] = idx_ss else: # 更新最长状态后, 完成此次比较(退出条件) max_len = max(max_len, len(hashtable)) idx_fs = hashtable[s[idx_ss]] + 1 break else: # 收尾: 特别处理, 没有走break # 一旦走到此处, 说明之后的比用在计算, 都比这次短 max_len = max(max_len, len(hashtable)) break return max_len ``` </div> </div> </div> --- ### 示例 ... THE END 本文作者:将夜 本文链接:https://zoe.red/2024/331.html 版权声明:本博客所有文章除特别声明外,均默认采用 CC BY-NC-SA 4.0 许可协议。 最后修改:2024 年 02 月 27 日 © 允许规范转载 赞 如果觉得我的文章对你有用,请随意赞赏