题目描述

题目链接：3.无重复字符的最长子串

算法原理

解法⼀：暴⼒求解（不会超时，可以通过）

枚举从每⼀个位置开始往后，⽆重复字符的⼦串可以到达什么位置。找出其中⻓度最⼤的即可。
在往后寻找⽆重复⼦串能到达的位置时，可以利⽤哈希表统计出字符出现的频次，来判断什么时候⼦串出现了重复元素。

解法二：滑动窗口

研究的对象依旧是⼀段连续的区间，因此继续使⽤滑动窗⼝思想来优化。
让滑动窗⼝满⾜：窗⼝内所有元素都是不重复的。
做法：右端元素ch进⼊窗⼝的时候，哈希表统计这个字符的频次：

• 如果这个字符出现的频次超过1 ，说明窗⼝内有重复元素，那么就从左侧开始划出窗⼝，直到ch 这个元素的频次变为1 ，然后再更新结果。
• 如果没有超过1 ，说明当前窗⼝没有重复元素，可以直接更新结果。

代码实现

解法⼀：暴⼒求解(时间复杂度为O(N²)，空间复杂度为O(1))

class Solution {
public:int lengthOfLongestSubstring(string s) {int res = 0;//记录结果for(int left = 0;left < s.size();left++){int hash[128] = { 0 };//记录每个字母的出现次数for(int right = left;right < s.size();right++){hash[s[right]]++;if( hash[s[right]] > 1){break;}res = max(res,right - left + 1);}}return res;}
};

解法二：滑动窗口(时间复杂度为O(N)，空间复杂度为O(1))

class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = { 0 };//记录每个字母的出现次数int res = 0;//记录结果for(int left = 0,right = 0;right < s.size();right++)//1.控制窗口的左右指针{hash[s[right]]++;//2.进窗口while(hash[s[right]] == 2)//3.判断{//出窗口hash[s[left]]--;left++;}res = max(res,right - left + 1);}return res;}
};