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

小咪咪 2022-12-02 04:21 43阅读 0赞

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从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: 1
    Explanation: The answer is "b", with the length of 1.
    Example 3:
    
    Input: "pwwkew"
    Output: 3
    Explanation: 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，那么我们它的所有子串应该有![image][]

种。再乘上我们遍历这个子串时候的长度，所以最后的结果是:

![image][image 1]

![image][image 2]

显然这样的复杂度是无法接受的，下面我们进行第一个优化。思考一个问题，**在不能有重复字符的限制下，我们真的有必要枚举所有的子串吗？其实是没有的，在这个规则的限制下，对于字符串当中的每一个起始位置，我们能找到的最长的合法子串必然是确定而且是唯一**的。换句话说，对于一个确切的开头而言，我们只需要顺着它一直往后遍历，如果遇到的字符没有出现过就继续，如果已经出现过了，那么当下的字符串就是这个开头对应的最佳答案。我们用样例举个例子：假设S=abcabcbb我们从S\[0\]开始，我们遍历b，再遍历c，接着遍历a。a已经出现过了，所以abc就是以S\[0\]开头的最佳答案。对于S当中的每一个位置，我们都可以找到它对应的局部最佳答案。之后，我们只需要在这当中找出最大的长度即可。我们用Python写出代码：

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次，所以整体的复杂度应该是![image][image 3]

。

到这里，基本上是我们通过平常思维能够想到的极致了，但是它远不是算法的极值。这道题还存在很大的优化空间，在我们继续探索之前，我们需要先来学习一个新的算法。它的名字叫做“**尺取法**”，在一些课本当中也被称为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\]开始，**通过移动的方式遍历出所有的合法区间**。这些合法区间当中，一定有一个是最终的答案，那么我们的问题也就解决了。

我们再来看一下这种算法的复杂度，它的复杂度是![image][image 4]

。有人会说，我们用了两个指针，不应该也是![image][image 5]

的复杂度吗？其实不然，看复杂度不能简单只看用了几个循环变量，而需要分析算法当中究竟执行了多少计算量。怎么证明算法复杂度呢？我们怎么知道窗口到底移动了多少次呢？

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

的算法。

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

也很简单，我们维护一个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

代码看起来依然很简洁，编码复杂度几乎没有增加。到这里，我们虽然已经将算法优化成了![image][image 7]

，但是并没有结束，这题**还有优化的空间**。那么，怎么做进一步优化呢？敏感的同学在观察上面这段代码的时候，可能会觉得中间的while循环有点别扭。虽然我们经过分析l最多也就移动到r的位置，不会出现越界等问题，但看到循环里套了循环还是会觉得不太舒服。我们的下一个优化，就和这个循环有关。那么怎么才能把循环去掉呢？我们先从它产生的原因入手，我们之所以需要一个循环，是因为我们并不知道引起重复的S\[r\]这个字符在区间里出现的位置在什么地方，如果我们能够知道，那么就很简单，我们**直接把l移动到它的右边即可**。我们能不能知道呢？当然是可以的，需要我们对dict做一点点改动。我们dict不能再存储字符出现的次数，我们需要存储它最后一次出现的位置。这样，我们对上面的代码稍作修改就可以满足要求了：

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

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

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

**上期推文：**

[LeetCode刷题实战1：在数组上遍历出花样][LeetCode_1]

[LeetCode刷题实战2：用链表模拟加法][LeetCode_2]

![image][image 8]

[image]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy80ODUzMDQ5LTVkYWE5ZmE0MjA1ZDNiNWE?x-oss-process=image/format,png
[image 1]: /images/20221123/ea3935e3b6274d1695fef1450dd2e406.png
[image 2]: /images/20221123/256646c8fd55486e83958a62e5ab106e.png
[image 3]: /images/20221123/e17216f7480a49d3a202c28e1e37a63d.png
[image 4]: /images/20221123/20dc37ea3cbe4b25baa3d5d1b40acee5.png
[image 5]: /images/20221123/b980dc2a45474740b4a49714b370d70b.png
[image 6]: /images/20221123/b2910c9f665f483986ee10333a08ceea.png
[image 7]: /images/20221123/f547f95c50264af6877240bfad375714.png
[LeetCode_1]: http://mp.weixin.qq.com/s?__biz=MzA5NzgzODI5NA==&mid=2454046571&idx=4&sn=e3feaa51aa57d4896d23752e7ec8335d&chksm=872bd2d2b05c5bc40e94fc4398f1be4eb1a6721a259a01ec006106892f53ccab96328a209925&scene=21#wechat_redirect
[LeetCode_2]: http://mp.weixin.qq.com/s?__biz=MzA5NzgzODI5NA==&mid=2454046630&idx=4&sn=00ead373609bb995600409688ff62015&chksm=872bd21fb05c5b09f283fae7880dce5a3086e950fd83d4b3623cef2e199efbfbefe460a8b12e&scene=21#wechat_redirect
[image 8]: /images/20221123/318b869321824ddfaeb14adba14c6b42.png