【leetcode复健-6】无重复字符的最长字串-滑动窗口的运用

3. 无重复字符的最长子串 - 力扣LeetCode摘要本文我将分享解决「无重复字符的最长子串」这道力扣题目的核心思路。我会重点讲解滑动窗口与哈希字典的结合使用并剖析一个关键陷阱遇到重复字符时不应丢弃整个当前子串而应巧妙地更新窗口左边界。通过变量x记录无效字符边界我们可以在一次遍历中高效求解。文末提供了可直接运行的 Python 代码实现。给定一个字符串s请你找出其中不含有重复字符的最长 子串的长度。示例 1:输入: s abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 abc所以其长度为 3。 注意 bca 和 cab 也是正确答案。示例 2:输入: s bbbbb 输出: 1 解释: 因为无重复字符的最长子串是 b所以其长度为 1。示例 3:输入: s pwwkew 输出: 3 解释: 因为无重复字符的最长子串是 wke所以其长度为 3。 请注意你的答案必须是 子串 的长度 pwke 是一个子序列不是子串。正解class Solution: def lengthOfLongestSubstring(self, s: str) - int: hash1 {} max_len 0 cur_len 0 x -1 for i in range(len(s)): if s[i] not in hash1: hash1[s[i]] i cur_len 1 elif hash1[s[i]] x: hash1[s[i]] i cur_len 1 else: x hash1[s[i]] cur_len i - hash1[s[i]] hash1[s[i]] i max_len max(cur_len, max_len) return max_len坑点与要点这道题首先有两个要求1. 只要求给出最长字串的长度2. 字串中不含重复字符这道题最坑的地方在于当一个字串中出现重复字串时我们会下意识的把这段子串完全丢弃并从改字串的下一个字符开始寻找下一个字串。然而这是错的这么做会导致我们丢失一大段已经寻找到的无重复字符的子串。因此对于一个出现重复字符的子串来说重复的字母一定位于该字串的首尾位置此时我们应该只抛弃该字串的头字符并接续着往下继续寻找无重复字符的字串而不是整段抛弃。如下a s d f g h j k l a z x c v当前遍历发现第二个a最大长度9|| ||重复 发现重复截断第一个字符a新子串 s d f g h j k l a z x c v当前遍历到v最大长度13解答思路使用滑动窗口把视线聚焦于不重复的那一段子串中遇到重复的字符从被重复的字符右边开始继续统计字符长度这就要求我们需要知道重复字符的位置当前子串的长度变为两个重复字符的下标之差因此我们使用字典。key为字符value为下标这里需要额外注意一点我们使用字典记录所有已出现的字符会造成一个问题对于 a b c d c b这段字符串当我们遇到第二个c时字典中a, b, c这三个键值对都应该被舍弃避免影响后续哈希判断但是我们无法准确的丢弃这些字符且IO开销过大因此我们需要一个额外的变量 x 用于记录第一个 c 的下标判断重复时下标小于 x 的字母自动认为不存在字典中如此以来就完成了舍弃操作。代码思路如下# 一张hash1表 字典# 一个变量x记录被重复字符下标# 最大长度max_len, 当前长度cur_len# 遍历一次每次判断当前字母i是否存在于hash1中# 如果不在则按照 字符下标 的形式存入字典 cur_len 1# 如果在但是hash1[s[i]] x 1# 则同样则按照 字符下标 的形式存入字典 cur_len 1# 如果在则 cur_len i - hash1[s[i]]# hash1[s[i]] i# 每次遍历末尾更新max_len代码实现class Solution: def lengthOfLongestSubstring(self, s: str) - int: hash1 {} max_len 0 cur_len 0 x -1 for i in range(len(s)): if s[i] not in hash1: hash1[s[i]] i cur_len 1 elif hash1[s[i]] x: hash1[s[i]] i cur_len 1 else: x hash1[s[i]] cur_len i - hash1[s[i]] hash1[s[i]] i max_len max(cur_len, max_len) return max_len