中国肩章大全图解,seo排名点击软件,易语言做网站视频,51com个人主页登陆3. 无重复的最长子串 难度#xff1a;中等难度 力扣地址#xff1a;https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/ 题目看起来简单#xff0c;刷起来有好几个坑#xff0c;特此记录一下#xff0c;解法比官网的更加简单中等难度 力扣地址https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/ 题目看起来简单刷起来有好几个坑特此记录一下解法比官网的更加简单可读性强。时间复杂度与空间复杂度与官方一样。
问题描述
给定一个字符串 s 请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1: 输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”所以其长度为 3。 示例 2: 输入: s “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”所以其长度为 1。 示例 3: 输入: s “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”所以其长度为 3。 请注意你的答案必须是 子串 的长度“pwke” 是一个子序列不是子串。 提示
0 s.length 5 * 1 0 4 10^4 104s 由英文字母、数字、符号和空格组成。
问题分析 解决方法
结合示例 1我做了一个详细的双指针移动 PPT 示意图。
解题代码
请小伙伴们结合上面的PPT进行理解以下内容包括两种方法第一种是基于哈希表第二种使用 vector 替代哈希表更快更节省资源时间复杂度不变
方法一基于 unordered_map 记录历史 双指针一次遍历
class Solution {
public:int lengthOfLongestSubstring(string s) {// 用于记录每个字符最后一次出现的索引unordered_mapchar, int map;// 最终结果int result 0;// 指针的开始位置我们最终要求的无重复字符的最长子串的开始位置// 这个指针将会根据实际情况而移动方向是一直向右int start 0;// 一次遍历所有字符// 遍历过程中主要处理两个事情// 1. 移动 start 指针// 2. 计算现在已知的最长子串的长度for (int i 0; i s.length(); i) {// 查找历史中该点auto tmp map.find(s[i]);// 如果历史中存在数据需要更新 start 的位置表示新的最长子串的开始位置// 需要注意的是更新后的start 必须越来越大即向右边移动避免 start 向左边移动if (tmp ! map.end()) {start max(tmp - second 1, start);}// 更新最后的结果即最长子串的长度result max(result, i - start 1);// 写入/更新 s[i] 字符的索引map[s[i]] i;}return result;}
};时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( ∑ ) O(\sum) O(∑)其中 ∑ \sum ∑ 表示字符集即字符串中可以出现的字符∣ ∑ \sum ∑∣ 表示字符集的大小。在本题中没有明确说明字符集因此可以默认为所有 ASCII 码在 [0,128) 内的字符即 ∣Σ∣128。我们需要用到哈希集合来存储出现过的字符而字符最多有 ∣ ∑ \sum ∑∣ 个因此空间复杂度为 O(∣ ∑ \sum ∑∣)。 方法二基于 vector 记录历史 双指针一次遍历
class Solution {
public:int lengthOfLongestSubstring(string s) {// 用于记录每个字符最后一次出现的索引vectorint lastIndex(256, -1);// 最终结果int result 0;// 指针的开始位置我们最终要求的无重复字符的最长子串的开始位置int start 0;// 一次遍历所有字符for (int end 0; end s.length(); end) {// 更新 start 的位置if (lastIndex[s[end]] ! -1) {start max(lastIndex[s[end]] 1, start);}// 更新最后的结果即最长子串的长度result max(result, end - start 1);// 更新 s[end] 字符的索引lastIndex[s[end]] end;}return result;}
};时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( ∑ ) O(\sum) O(∑)其中 ∑ \sum ∑ 表示字符集即字符串中可以出现的字符∣ ∑ \sum ∑∣ 表示字符集的大小。在本题中没有明确说明字符集因此可以默认为所有 ASCII 码在 [0,128) 内的字符即 ∣Σ∣128。我们需要用到哈希集合来存储出现过的字符而字符最多有 ∣ ∑ \sum ∑∣ 个因此空间复杂度为 O(∣ ∑ \sum ∑∣)。
总结
这道题目通过简单的双指针和哈希表的结合可以高效地解决字符串中无重复字符的最长子串问题。这种方法的时间复杂度为O(n)因为每个字符在最坏情况下也只会被访问两次一次作为结束字符一次作为开始字符。空间复杂度为O(1)因为哈希表的大小是固定的最多为256个字符。
也正是基于这个原因后面我们增加了使用 vector 提到哈希表可以更加节省资源以及查找历史的时间。 Smileyan 2024.06.29 22:59
