尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
【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
RELATED

相关推荐

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

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

1. 从统计模型到基因组大模型:一场预测范式的深刻变革如果你最近在关注基因组学,尤其是转录组和RNA剪接领域,那么“AI预测可变剪接”这个话题一定绕不开。从早期的隐马尔可夫模型(HMM)到如今动辄数十亿参数的基因组大模…

📅 2026/10/7 0:00:24
大模型后训练:离策与在策学习统一框架与工程实践

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

1. 项目概述:后训练时代的核心命题如果你在过去一年里深度参与过大语言模型(LLM)的应用或微调,大概率会陷入一个选择困境:手头有一批高质量的指令数据,是应该直接拿这些数据去微调模型(这通常被…

📅 2026/11/10 14:03:52
大语言模型评估陷阱:为何追求准确性反而催生幻觉?

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

1. 当“正确”成为陷阱:重新审视大语言模型的评估范式最近和几个做模型评测的朋友聊天,大家不约而同地提到一个现象:我们花大力气设计的那些“准确性”评测集,好像正在把模型往一个奇怪的方向上推。你让模型做数学题,它…

📅 2026/9/16 22:35:42
MORE NEWS

更多资讯

📰

辽宁东港办电工证怎么报名才不踩坑?实操考试心里没底怕挂科?

辽宁东港办电工证怎么报名才不踩坑?实操考试心里没底怕挂科? 你是不是也遇到过这种情况:听说要考电工证了,心里直打鼓,怕实操考试挂科,怕流程复杂,怕报名信息填错了?别慌,今天就从一个真实的案例出发,给你讲清楚 辽宁东港办电工证…

📰

工地太忙根本没时间复习考试?涪陵安监局考电工证官方报名入口全攻略

工地太忙根本没时间复习考试?涪陵安监局考电工证官方报名入口全攻略 工地太忙根本没时间复习考试?你不是一个人,很多人都在为【涪陵安监局考电工证】犯愁,尤其是像我们这种长期在工地一线的电工,工作节奏快,任务紧,哪还有时间去复习备考?但别担心,今…

📰

石家庄在哪学电工证?2026河南最新政策来了,别让工地太忙耽误你考证

石家庄在哪学电工证?2026河南最新政策来了,别让工地太忙耽误你考证 工地太忙根本没时间复习考试,这话我听得太多了。作为一名在郑州金水区从事中小施工企业管理的老油条,我知道特种作业证对咱们一线工人来说有多重要,特别是电工证,不仅是上岗的“门…

📰

玻璃厂电工证工资多久拿证?证书过期了不知道怎么复审延期

玻璃厂电工证工资多久拿证?证书过期了不知道怎么复审延期 你是不是也遇到过这种情况:电工证到期了,想复审却不知道流程?玻璃厂电工证工资多久拿证?这些问题,其实都和你是否清楚特种作业操作证的管理规则有关。别担心,下面一步步告诉你怎么解决。…

📰

特高压电工证丢了咋办怎么报名流程全解析

特高压电工证丢了咋办怎么报名流程全解析 之前考的证在外省能不能转过来?这个问题在特高压电工圈里太常见了。很多人因为工作调动、搬家等原因,手里原本的电工证突然变得“不香了”。特高压电工证丢了咋办,是很多人正在经历的现实问题。别急,这篇文章就帮…

📰

罗定考电工证视频官方报名入口怎么找?别被中介忽悠了

罗定考电工证视频官方报名入口怎么找?别被中介忽悠了 你是不是正盯着手机屏幕,想考个电工证,但又不知道去哪报名,怕被中介坑?别急,我来告诉你怎么绕开这些陷阱,找到 官方报名入口 ,顺利拿到你的电工证。 先说重点: 罗定考电工证视频…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬