LeetCode刷题实战3：最长不重复子串

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做最长不重复子串，这道题很有意思，我们先来看题面：

Given a string, find the length of the longest substring without repeating characters.

https://leetcode.com/problems/longest-substring-without-repeating-characters/

翻译

题目只有一句话：给定一个字符串，要求返回不包含重复字符的最长子串的长度。

Example 1:
Input: "abcabcbb"Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2:
Input: "bbbbb"Output: 1Explanation: The answer is "b", with the length of 1.Example 3:
Input: "pwwkew"Output: 3Explanation: The answer is "wke", with the length of 3.              Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

分析

我们先从最简单的方法开始，最容易想到的算法就是暴力枚举。我们可以遍历出这个字符串当中所有的子串，之后再判断这个子串当中有没有出现重复的元素。如果没有重复的元素，那么我们就更新答案。

在开始编码之前，我们先仔细观察样例：

我们可以计算出这种算法的复杂度，假设字符串长度是n，那么我们它的所有子串应该有种。

ret = 0
for i in range(n):
    char_set = set()
    mid_ret = 0
    for j in range(i + 1, n):
        if S[j] in char_set:
            mid_ret = j - i
            break
        else:
            char_set.add(S[j])
    ret = max(mid_ret, ret)
return ret

这种方法的复杂度就很好算了，对于S而言，它一共有n个位置可以作为起始，每个起始位置，最多遍历n次，所以整体的复杂度应该是。

到这里，基本上是我们通过平常思维能够想到的极致了，但是它远不是算法的极值。这道题还存在很大的优化空间，在我们继续探索之前，我们需要先来学习一个新的算法。它的名字叫做“尺取法”，在一些课本当中也被称为two pointer算法或者是两指针算法，也叫滑动窗口算法。

算法的本意是，在一些对区间有所限制的问题当中，我们可以通过维护合法区间的左右边界。通过区间移动找出所有合法的区间，最后找到最终的答案。

在本题当中，我们可以把一个不包含重复字符的子串当做是原字符串的一个合法区间。比如在字符串 “abcabcbb” 当中[0, 2]就是一个合法区间。我们用两个记录下标的指针l和r来记录这个区间的左右端点，注意这里的区间我们用的是闭区间。也就是说 l=0，r=2，区间表示好了，怎么移动区间呢？

[a b c] a b c b b

很简单，我们每次往右移动一位，也就是r += 1，区间变成：

[a b c a] b c b b

r往右移动一位，就会读入新的字符，那样整个区间的合法性可能就破坏了。比如我们r加1了之后，读入了a，字符串中多了一个a，那就不是合法区间了。

没关系，我们还有区间的左边界，我们可以再移动区间的左边界，退出一些字符，直到区间重新变成合法区间为止，在这个例子当中，l只需要移动一位就可以满足条件：

a [b c a] b c b b

也就是说新的区间变成了[1, 3]，这样就完成了区间的移动。如果r移动了之后，依旧没有出现重复字符呢？没关系，我们继续往下移动就可以了。在这题当中，[0, 0]一定是一个合法的区间，我们可以从[0, 0]开始，通过移动的方式遍历出所有的合法区间。这些合法区间当中，一定有一个是最终的答案，那么我们的问题也就解决了。

我们再来看一下这种算法的复杂度，它的复杂度是。有人会说，我们用了两个指针，不应该也是的复杂度吗？其实不然，看复杂度不能简单只看用了几个循环变量，而需要分析算法当中究竟执行了多少计算量。怎么证明算法复杂度呢？我们怎么知道窗口到底移动了多少次呢？

不知道移动了多少次也可以，方法很简单，我们分析最坏的情况。算法的起始状态是l=0, r=0。当r=n时算法结束，我们不知道此时l等于多少，不过没关系。在算法运行的当中，l和r都是递增的，每次窗口移动最多增加1，那么最多应该执行了2n次（l和r各移动n次）。如此一来，显然这是一个的算法。

算法讲完了，还有一个细节没讲清楚，我们怎么维护区间合法呢？

也很简单，我们维护一个map，记录区间内的字符出现了多少次。我们遇到新的字符，就在map中加一，退出字符，就在map中减一。

Talk is cheap, show me the code。我们写出code来看看：

l, r = 0, 0
ret = 0
char_dict = {}
char_dict[S[0]] = 1
for r in range(1, n):
    char_dict[S[r]] += 1
    # 当S[r]位置的字符大于1，说明区间非法，开始移动区间左侧
    # 最多l=r时结束，不用担心越界
    while char_dict[S[r]] > 1:
        char_dict[S[l]] -= 1
        l += 1
    ret = max(ret, r - l + 1)
return ret

代码看起来依然很简洁，编码复杂度几乎没有增加。到这里，我们虽然已经将算法优化成了，但是并没有结束，这题还有优化的空间。

l, r = 0, 0
ret = 0
char_dict = {}
char_dict[S[0]] = 0
for r in range(1, n):
    # char_dict[S[r]] >= l这个判断是精髓
    if S[r] in char_dict and char_dict[S[r]] >= l:
        l = char_dict[S[r]] + 1
    char_dict[S[r]] = r
    ret = max(ret, r - l + 1)
return ret

到这里，这道题就算是讲解完了。尺取法这个算法虽然不难，但是仔细琢磨挺有意思。如果有没有理解的同学，可以结合代码以及样例仔细思考一下，算法不难，我想大家都能学会，衷心希望大家都能有所收获。

如果喜欢本文，请顺手点个赞或者转发吧。