番禺网站建设培训学校中国机械加工网易下拉方法

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_set<char> 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快烧干了，整个人都不好了。

知识储备还得多补充。。。

明天继续加油吧。