收录于专栏【经典算法练习】

枚举[从每一个位置]开始往后,无重复字符的字串可以到达什么位置.找出其中长度最大的即可.

在往后寻找无重复字串能到达的位置时,可以利用[哈希标]统计出字符出现的频次,来判断什么时候字串出现了重复元素.

具体步骤

定义两个指针i,j遍历数组j,向后移动寻找与i重复的数j找到与i相同的数,更新字串长度.然后i,j

代码展示

lengthOfLongestSubstring(string

{int

我们暴力枚举的时间复杂度为O(N^2),这样数据级别大于10^9小于10^10是有机会通过的.

如果这道题更狠的话,直接把数据修改为10^5之内的字符,那我们的暴力枚举直接退役了

解法二(滑动窗口)

研究的对象依旧是一段连续的区间,因此继续使用[滑动窗口]思想来优化.

让滑动窗口满足:

如果这个字符出现的频次超过1,说明窗口内有重复元素,那么就从左侧开始划出窗口.直到right这个元素的频次变为1,然后更新结果.

基本思路:

lengthOfLongestSubstring(string

{int

n){hash[s[right]];while(hash[s[right]]

hash[s[left]]--;ret

我们开了一个hash数组,但只有128个空间,也就是常数级别,可以忽略不记,所以时间复杂度为O(1)