3.无重复字符的最长子串 Longest Substring Without Repeating Characters

太过爱你忘了你带给我的痛 2022-12-29 01:56 88阅读 0赞

## 题目描述 ##

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

**示例 1**:

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

**示例 2**:

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

**示例 3**:

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

示例 4:

> 输入: s = “”  
> 输出: 0

来源：力扣（LeetCode）[链接][Link 1]

## 第一次题解 ##

执行用时：72 ms, 在所有 Python3 提交中击败了72.55%的用户；内存消耗：14.9 MB, 在所有 Python3 提交中击败了5.13%的用户。开始做的时候不知道滑动窗口算法。

class Solution:
        def lengthOfLongestSubstring(self, s: str) -> int:
            s = list(s)
            l1 = []
            maxlength = 0
            for i in range(len(s)):
                if l1.__contains__(s[i]):  # 出现重复元素，寻找下一个子串，初始化l1
                    index = l1.index(s[i])
                    l1 = l1[index + 1:]    # 找到重复元素的索引将下一个索引赋值给新l1
                    l1.append(s[i])
                else:    # 没有出现重复元素
                    l1.append(s[i])
                    if len(l1) > maxlength:
                        maxlength = len(l1)
            return maxlength

## 最优题解 ##

> **滑动窗口算法**：类似滑动窗口协议，滑动窗口算法是指在给定特定窗口大小的数组或字符串上执行要求的操作。该技术可以将一部分问题中的嵌套循环转变为一个单循环，因此它可以减少时间复杂度。其时间复杂度为O(n)。  
> 参考博客：[滑动窗口算法基本原理与实践][Link 2]

滑动窗口算法题解：执行用时：60 ms, 在所有 Python3 提交中击败了92.86%的用户；内存消耗：15 MB, 在所有 Python3 交中击败了5.13%的用户。

class Solution:
        def lengthOfLongestSubstring(self, s: str) -> int:
            if not s:
                return 0
            lookup = set()
            left = 0
            max_len = 0
            cur_len = 0
            for i in range(len(s)):
                cur_len += 1
                while s[i] in lookup:
                    lookup.remove(s[left])
                    left += 1
                    cur_len -= 1
                if max_len < cur_len:
                    max_len = cur_len
                lookup.add(s[i])
            return max_len

[Link 1]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
[Link 2]: https://www.cnblogs.com/huansky/p/13488234.html