【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

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

相关推荐

AI预测可变剪接：从统计模型到基因组大模型的演进与实践指南

大模型后训练：离策与在策学习统一框架与工程实践

大语言模型评估陷阱：为何追求准确性反而催生幻觉？

更多资讯

射频开关与功率检波器协同设计实战指南

如何快速保证 3D 打印质量？text-to-cad G-code 校验机制与 6 项自动检查详解

心理咨询师个人体验与督导的重要性解析-中国心理学会心理咨询师水平评价-长春心理咨询培训机构

TCS3720与R7KA8D2KFLCAC工业级光感协同设计指南

心理咨询师考试一年考几次？2026年考试时间安排全攻略-中国心理学会心理咨询师水平评价-长春心理咨询培训机构

基于YOLOv8的航拍温室大棚智能检测系统开发实战

今日更新

基于MATLAB的CRI显色指数计算：从SPD光谱到Ra的完整流程

JSP+Servlet+MySQL博客系统源码部署与优化全攻略

蜂窝调度算法 MATLAB 实现：比例公平、轮询与最大 C/I 对比

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？