LeetCode 刷题：3. 无重复字符的最长字串

这题比前两题要难，用到了第一题的哈希表方法，暴力算法比较好想但费时，第二种方法较为巧妙。

标题	无重复字符的最长子串
序号	NO.3
难度	中等
标签	哈希表 字符串 滑动窗口

1. 题目

---

给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 代码

---

方法一：暴力求解

看到这题，我首先想到的是用两层 for 循环求出所有子串，然后结合第一题的思路，运用哈希表判断该字串是否符合无重复字符的要求。

两层 for 循环时间复杂度为 O (n²)，哈希表时间复杂度为 O (n)，所以总的时间复杂度上升到了 O (n³)，显然不是一个好的解决办法。用 Python 写了一下，果不其然，耗时 8s, 击败 5% 的提交用户🥲。

• 时间复杂度 O (n³)

• 空间复杂度 O (n)

• 执行用时：8784ms

• 内存消耗：15MB

class Solution:

    def Is_not_reduplicated(self, s):
        dic = {}
        for i in s:
            if i in dic:
                return False
            else:
                dic[i] = 1
        return True

    def lengthOfLongestSubstring(self, s: str) -> int:
        length = len(s)
        num = 0
        for i in range(length):
            for j in range(1, length - i + 1):
                # print(s[i:i + j])
                if self.Is_not_reduplicated(s[i:i + j]):
                    if j > num:
                        num = j
                else:
                    break

        return num

方法二：滑动窗口

实在时没想到别的方法，于是便看了讲解，看完之后就一个字：妙！

设置两个左右指针，右指针依次向右，用哈希表法确定左右指针中的字符是否存在重复，若存在重复，则移动左指针，始终确保左右指针中的字符不存在重复即可。

• 时间复杂度 O (n)

• 空间复杂度 O (n)

• 执行用时：56ms

• 内存消耗：15MB

class Solution:

    def lengthOfLongestSubstring(self, s: str) -> int:
        start, num, max = 0, 0, 0
        dic = {}
        for i, x in enumerate(s):
            if x in dic:
                if dic[x] + 1 > max:
                    start = dic[x] + 1
                    max = start
                else:
                    start = max

            dic[x] = i

            interval = i - start + 1
            if interval > num:
                num = interval
        return num

需要特别注意的是，左指针的移动并不是简单的 +1， 具体可参考 "abba" 这个字符串用例。