给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
解题思路1:直接暴力枚举每一个字符,然后在枚举这个字符的后面每一个字符,即可获得答案
- class Solution {
- public:
- int lengthOfLongestSubstring(string s)
- {
- int res = 0;
- for(int i = 0;i < s.length();i ++)
- {
- unordered_set<char>has;
- int j = i;
- while(j < s.size() && !has.count(s[j])) has.insert(s[j ++]);
-
- res = max(res , j - i);
-
- }
- return res;
- }
- };
时间直接到达744ms,直接冲破天际,因此需要优化。
解题思路2:滑动窗口来优化这个代码,移动窗口只需将最左边的元素,移除has就行,字串的长度就是两个左右端点的坐标相减。
- class Solution {
- public:
- int lengthOfLongestSubstring(string s)
- {
- int res = 0;
- int j = 0;//充当左指针
- unordered_set<char>has;
- for(int i = 0;i < s.length();i ++)
- {
- while(has.count(s[i])) has.erase(s[j ++]);
- has.insert(s[i]);
- res = max(res , i - j + 1);
- }
- return res;
- }
- };
这个思路时间减少到28ms,直接提升了很多。