做网站推广送什么,上海到北京高铁票价多少,分类信息网站成都搭建,管理网络的应用软件文章目录 1.题目示例提示 2.解答思路3.实现代码结果 4.总结 1.题目
给定一个字符串 s #xff0c;请你找出其中不含有重复字符的 最长子串 的长度。
示例
示例 1: 输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”#xff0c;所以其长度为 3。
示… 文章目录 1.题目示例提示 2.解答思路3.实现代码结果 4.总结 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 * (10^4)s 由英文字母、数字、符号和空格组成
2.解答思路
滑动窗口:
滑动窗口主要应用在数组和字符串上。遍历一个序列时可以类比成队列只能队尾进队,对头出队一个队头指针left一个队尾指针right
针对本题分析
1.队头指针left先固定向右移动队尾指针right直至出现重复的字符计录下此时队列长度。 2.对头指针left向后移动直至没有重复字符出现再插入此时的队尾指针right所指字符。 3.比较记录下的队列长度的最大值就是无重复字符的最长字串长度。
代码所需知识汇总
关于字符串string s s.size();//返回字符串长度 s[i] //调用下标为 i 的字符 更多字符串的成员函数见文章C字符串的常用操作函数全总结
关于集合 头文件#include unordered_set unordered_set char str; // 定义一个char类型的无序集合 str.insert(s[i]); //在集合中插入s[i] str.find(s[i]); //在集合中查找s[i]字符若存在会返回相应下标若不存在会返回str.end() str.end(); //表示集合的最后一个元素的后面 str.erase(s[i]); //删除s[i]所对应字符的下标对应字符
3.实现代码
class Solution
{
public:int lengthOfLongestSubstring(string s){int n s.size();if (n 0 || n 1)return n;unordered_setchar str; // 无序集合int maxLength 0; // 记录最大值int count 0; // 记录每次的子串长度// i是队头下标j是队尾下标for (int i 0, j 0; j n; j){// 在队列找到了对应字符 while (str.find(s[j]) ! str.end()){// 需要队头指针向后移直至队尾元素在子串中没有重复的字符str.erase(s[i]);//删除对头下标对应字符i;//对头后移一位count--;//子串字符长度减少一位}str.insert(s[j]);//将队尾所指字符插入子串strcount;if (count maxLength)maxLength count;}return maxLength; }
};结果 2024.2.5优化部分代码后运行时间降低
4.总结
今天这题做了好长时间cpu快烧干了整个人都不好了。
知识储备还得多补充。。。
明天继续加油吧。
