【LeetCode滑动窗口专题#2】无重复字符的最长子串
2023/6/9 5:23:13
本文主要是介绍【LeetCode滑动窗口专题#2】无重复字符的最长子串,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#1传送门
滑动窗口最大值
长度最小的子数组
无重复字符的最长子串
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
提示:
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
思路
容易想到这里需要使用滑动窗口的思想来解决问题
我们可以定义两个指针,left和right
left一开始指向0,right则放入for循环中向前不断遍历字符串s
这里还需要维护一个哈希表(选择map,因为字符类型不止有26个字母)
使用当前遍历值(字符)在表中查询,如果没出现过,就把当前字符放入哈希表中
注意!!!!!!
这里有可能我们会下意识的将哈希表的键值结构定义为:"遍历字符--字符出现次数"
在本题中,这是错误的,或者说是不合适的
因为我们需要找到重复字符第一次出现的位置,如以字符出现次数为值的话,无法实现这一目的(字符出现位置可以帮助我们确定哪个字符是第一个不重复的字符)
举个例子,假设有字符串 "abccba",如果我们以字符出现次数为值来构建哈希表,那么哈希表的值应该为 {'a': 2, 'b': 2, 'c': 2},这些字符的出现次数都是相同的。如果我们想要找到第一个不重复的字符,就需要进一步遍历原字符串,找到第一个出现次数为1的字符。但是,如果我们以字符出现位置为值来构建哈希表,那么哈希表的值应该为 {'a': 0, 'b': 1, 'c': 2},我们可以在遍历字符串的过程中实时更新哈希表,并找到第一个出现位置最小的字符。
因此,在这个问题中,以字符为键,以字符出现位置为值("遍历字符--字符首次出现位置")是更加合适的选择。
继续
如果当前遍历值在表中出现过,那么我们在哈希表中获取该字符对应的值,即其在s中第一次出现的位置
将左指针移动到该位置(为什么?),并且加1跳过该位置,目的是剔除重复值
这里是本题的第二个坑
在写的时候,第一版中我移动left时用了left++,但是这样是错的,不能简单地使用left++来移动左指针,因为有可能之前的某个字符已经出现过,那么我们需要更新左指针的位置,使得新的左指针位置可以舍弃之前出现过的字符,从而保证当前的子串不重复。
这其实还涉及到我们如何定义“重复出现”这件事情
因为在设计hash表时,保存的是当前字符的索引,因此,我们仅仅在hash中查询到某个字符还不够,原因如下:
如果当前字符s[right]已经在哈希表中存在,则说明该字符之前出现过,我们需要更新左指针的位置,使其跳过该重复字符,即左指针left的新位置应该是(hash[s[right]]+1)。但是,在更新左指针的同时,还需要确保新的左指针位置大于等于上一个子串的起始位置left,因为我们要寻找最长的无重复子串,而不仅仅是子串长度。
因此,
hash.find(s[right]) != hash.end() && hash[s[right]] >= left
确保了字符s[right]曾经出现过(也就是该字符在哈希表中有对应的索引),并且其最后一次出现的下标大于等于当前子串的起始位置left,才会更新左指针的位置。如果只写
hash.find(s[right]) != hash.end()
的话,可能会把之前的那些已经被跳过的字符再次算进去,从而导致错误的结果。例如:"abcabcbb"
如果当前左指针指向的是第一个b,右指针指向第二个a,说明我们已经判断a重复出现,并把左指针移动到了hash[s[right]]+1
此时我们并没有删除hash表中关于a第一次出现的位置信息,因此下一次如果还遇到a,我们不能让左指针移动到第一次a的位置
所以需要加上限定条件,即
hash[s[right]] >= left
来保证左指针的正常跳转
然后,更新当前字符在哈希表中的位置值,即将当前字符位置设置为第一次出现位置
代码
关键点:哈希表键值对设计(采用"遍历字符--字符首次出现位置")、left指针的移动方式
步骤:
1、定义一个哈希表,键为字符,值为字符出现的index
2、移动右指针遍历字符串s,在哈希表中查询当前遍历字符
如果有重复,同时判断该重复值位置是否大于left指针位置(因为如果出现重复值,left指针所值的应该是上一次该值出现的位置),大于则将left移动到当前字符位置,并加1跳过当前位置
如果无重复,先不处理
3、不管有无重复都对当前遍历字符在哈希表中的值(即位置索引)进行更新(同时也处理了无重复的情况)
4、左右指针作差与最大长度变量比较,并更新该变量
5、返回最大长度变量
class Solution { public: int lengthOfLongestSubstring(string s) { unordered_map<char, int> hash;//创建hash表 int left = 0;//左指针 int maxLen = 0; for(int right = 0; right < s.size(); ++right){//遍历字符串s if(hash.find(s[right]) != hash.end() && left <= hash[s[right]]){//若当前字符在哈希表中存在 left = hash[s[right]] + 1;//获取当前字符在哈希表中对应的值,该值为字符在s中的索引,将左指针移动到此处 //即若当前字符在哈希表中存在,我们需要将left指针指到重复字符s[right]上次出现的位置,然后加1来跳过它 } //对应情况:1、当前字符在哈希表中不存在/2、跳转left指针至重复值第一次出现位置之后,更新当前字符在哈希表中的位置信息 hash[s[right]] = right;//添加字符到哈希表/更新信息 if(right - left + 1 > maxLen) maxLen = right - left + 1;//更新当前最大长度 } return maxLen; } };
这篇关于【LeetCode滑动窗口专题#2】无重复字符的最长子串的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-13WebSocket学习:初学者必读的简单教程
- 2024-10-13第24/26集:TinyConf,ng-贝尔格莱夫,为什么要一直升级呢?
- 2024-10-13全面指南:在 Node 和 TypeScript 中设置 ESLint、Jest 和 Prettier
- 2024-10-12你可以借助 Claude-3 和 Lightning AI,将任何 YT 视频变成内容创作神器。
- 2024-10-12在 NVIDIA AI 的支持下,用 Llama3 在 VSCode 中当代码助手。
- 2024-10-12使用 llama.cpp 对大型语言模型(LLM)进行量化
- 2024-10-12RAG解决方案在Amazon Bedrock中的第八部分:将Amazon Cognito与Amazon EKS集成在一起
- 2024-10-12Databricks 资源包:部署工作流程
- 2024-10-12在这篇文章中,我们如何在 Apache Airflow 中调度 2000+ 个 DBT 模型?
- 2024-10-12亚马逊和谷歌对CI/CD的看法截然不同