关于3-8可以处理任意字符的改进(golang实现)
来源：3-8 在滑动窗口中做记录 Longest Substring Without Repeating Characters
yatkun
2017-10-21
老师使用的查找重复的字符是使用一个计数数组，我改成了直接遍历前面的字符是否与最右边的那个字符是否相同，相同的话，返回重复字符的索引，l直接前进到索引的下一个字符。这样查找重复元素的累计时间是n，所以最后的时间复杂度还是o(n)的。
func lengthOfLongestSubstring(s string) int {
str := []rune(s)
l, r := 0, 0 // str[l, ... r-1] 滑动窗口
res := 0
for r < len(str) {
isDup, index := isDuplicateChar(str, l, r)
if !isDup {
if r-l+1 > res {
res = r - l + 1
}
r++
} else {
l = index + 1
}
}
return res
}
// 新加入的str[r]是否和[l, r-1]之间的字符重复，如果重复，则返回重复字符的位置
func isDuplicateChar(str []rune, l, r int) (bool, int) {
for i := l; i < r; i++ {
if str[i] == str[r] {
return true, i
}
}
return false, -1
}
1回答
-
赞思路！
但其实，由于你的isDuplicateChar(str, l, r)函数是从l到r-1之间的一次遍历，在最坏情况下，整个字符串一直没有重复的字符的话，这个算法相当于对于每一个字符，都要将之前的字符串遍历一遍，成为了一个O(n^2)级别的算法。
当然了，对与大多数字符串，尤其是英文字符串，字符集数量非常有限，当n很大的时候，不可能整个字符串没有重复字符，所以准确地说，这是一个O(len(s)*len(charset))级别的算法。
我将这个思路实现了一遍，和我在课程中介绍的思路进行了性能对比，使用1000万的随机字符串进行测试。C++代码在这里：https://github.com/liuyubobobo/Play-with-Algorithm-Interview/blob/master/03-Using-Array/Course%20Code%20(C%2B%2B)/08-Longest-Substring-Without-Repeating-Characters/main_cmp.cpp
我在我的电脑上测试结果如下：
Test: 1,000,000 length of completely random string: algo1 : res = 49 Time = 1.10983 s // 我在课程中讲解的思路 algo3 : res = 49 Time = 3.09216 s // 你的思路
我的思路性能较优的原因，就在于我使用了查找表，预存了每一次的计算结果。所以当遇到新的字符的时候，不需要进行任何遍历操作，直接使用O(1)的时间去提取相应的信息。当然了，相应的代价就是，我的思路的算法空间复杂度是O(len(charset))，而你的思路的算法空间复杂度是O(1)。
另外，我曾经在这个课程的源码中添加过一个思路，见C++代码中的main3，其本质就是每次更新r以后，相应的l不是挪一步，而是挪x步，但是在挪的过程中要不断更新freq数组。这个思路在数据量大的情况下，效率更高哦，可以参见上面代码中的algo2的测试结果，源码见main3：）
至于你说的处理任何字符串的问题，其实只需要引入map就好了。下一章就会介绍：）
再次赞思路！
122017-10-22
相似问题