左边界l的位置问题

Question

根据老师前面的算法描述，当下一个字符是重复字符时，感觉‘l++’是不够的，l的下一个位置应该是与r+1相同的那个元素的下一个位置才对，是不是呀？

Answer 1

liuyubobobo 2018-06-27 17:39:32

赞！是的，l可以每次不加1，而是直接找到最合适的那个位置：）

对此，之前在一个同学的提问中，我特意进行了详细的阐述，并且也进行了详细的实现，具体可以参见这里：http://coding.imooc.com/learn/questiondetail/28609.html

对于这个问题，我给出了五种实现，其中对于l不+1，而是加到“更好”的位置，参见4，5两种实现。https://github.com/liuyubobobo/Play-with-Algorithm-Interview/tree/master/03-Using-Array/Course%20Code%20(C%2B%2B)/08-Longest-Substring-Without-Repeating-Characters

这里，要注意的是，第4个实现是最显而易见的实现这种思路的方式，但是由于每次都要确认一下l需要跳转的位置，其实整个程序的复杂度是更高的。第5个实现是相应的改进方式。每一种实现我都标有注释，可以参考：）

由于Leetcode上的问题，尤其是题号比较低的问题，测试数据都非常小，所以在leetcode上提交不太能看出这些不同实现之间的性能差距。我特别制作了一个生成更大数据的测试程序，使用1000万级别的数据来看这些实现之间的性能差距，有兴趣可以参考：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

加油！：）

• 提问者 MissSingleEyelid #1

  谢谢老师耐心又详细的讲解！