LeetCode 解题报告 (3)-- 双指针找最长不重复子串

发表于 标签 ， ，

原题如下

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

这道题是典型的找最长子字符串问题，就是要找出没有重复的最长子字符串。本文讲述了两种方法，一种时间复杂度为 \(O(n^2)\)，另一种的时间复杂度为 \(O(n)\)

最容易想到的方法就是遍历整个字符串，找出以每个字符开头的最长子字符串，再从中找出最长的子字符串。这样的时间复杂度是 \(O(n^2)\)，实现代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):  
    def lengthOfLongestSubstring(self, s):  
        """  
        :type s: str  
        :rtype: int  
        """  
        max=0  
        for  i in range(len(s)):  
           tmp=[]  
           tmp.append(s[i])  
           for j in range(i+1,len(s)):  
               if s[j] not in tmp:  
                   tmp.append(s[j])  
               else:  
                   if len(tmp)>max:  
                       max=len(tmp)  
                       break  
        return max

这种方法虽然易于理解，但是由于时间复杂度问题，运行超时。

现在再分析一下题目，是否有必要计算以每个字符开头的最长子字符串？

答案是不必要的。比如说对于字符串 abcdedfghi, 从 a 开始往后进行判断，则遇到第二个 d 的时候会发现与前面的 d 重复了，判断停止，那么以 a 开头的最长子字符串为 abcde，然后以一个新的字母开头找最长的子字符串。按照上面的方法，接下来会以 b 为开头找其最长子字符串。但是你会发现找到的最长子字符串肯定比以 a 开头的最长子字符串要短，原因是后面重复的元素位置没有变，而从 b 或 c 开始相当于把不重复的部分截断了。所以如果要找到可能更长的子字符串，必须要从与当前字符重复的字符往后的一个字符位置开始找，在本例中就是要从 e 开始找，才有可能找得到比以 a 开头的最长子字符串更长的子字符串。

这样，便可以通过找与当前字符重复的前一字符的位置来避免第二层的 for 循环，将时间复杂度缩短为 \(O(n)\)

通过双指针能够实现上面的功能，左右指针共同维护一个没有重复字符的子字符串，每当没有重复字符时，右指针一直往右移动；有重复字符时左指针往右移动直到左右指针之间没有重复字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):  
    def lengthOfLongestSubstring(self, s):  
        """  
        :type s: str  
        :rtype: int  
        """  
        left, right, n = 0, 0, len(s)  
        visited, result = set(), 0  
        while right < n:  
            if s[right] in visited:  
                while s[right] in visited:  
                    visited.remove(s[left])  
                    left += 1  
                visited.add(s[right])  
            else:  
                visited.add(s[right])  
                result = max(right-left+1, result)  
            right += 1  
        return result

上面的方法虽然能够 AC, 但是每次遇到重复元素时左指针往右一步一步地移动并删除元素的操作会比较慢，因此可以 通过 HashTable 存储每个元素的最大下标，遇到重复元素的时候判断前一重复元素位置的下标是否大于当前左指针位置，若是则更新左指针，否则不更新；同时更新 HashTable 当前重复元素的下标。下面是实现的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):  
    def lengthOfLongestSubstring(self, s):  
        """  
        :type s: str  
        :rtype: int  
        """  
        left, right,result= 0, 0, 0  
        indices = {}  
        while right < len(s):  
            if s[right] in indices and indices[s[right]] >= left:  
                result = max(result, right - left)  
                left = indices[s[right]] + 1  
            indices[s[right]] = right  
            right += 1  
        return max(result, right - left)