LeetCode3: Longest Substring Without Repeating Characters
题目:给定一个字符串,求最长的无重复字符的子串长。
例如,对于字符串”abcabcbb”,这样的子串就是”abc”,长度是3。对于字符串”bbbbb”,这样的子串就是”b”,长度是1。
这也是一个简单题。但是同样,O(n^2)的brute force解法是不能被接受的。可以注意到,题目里面给了一个标签是Two Pointers。这是一个很重要的提示。所谓双指针,就是在一个数组上维护两个位置信息,表示当前状态的一头一尾。
我们让指针A指向当前满足条件子串的开头,指针B指向当前满足条件子串的结尾。初始的时候两指针均指向开头。然后逐一向后移动B,每移动一次就检查该元素是否在之前已经出现。如果出现,刷新长度为max(指针B的位置减去指针A的位置, 当前长度),并且让指针A往后移动一位。
最终结果为max(字符串末尾减去指针A的位置,当前最大长度)