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

### 回答1： 可以使用以下代码来找到字符串s中不包含重复字符的最长子串的长度： ``` def lengthOfLongestSubstring(s): n = len(s) if n <= 1: return n left, right = 0, 0 max_len = 0 while right < n: if s[right] not in s[left:right]: right += 1 else: max_len = max(max_len, right - left) while s[left] != s[right]: left += 1 left += 1 right += 1 return max(max_len, right - left) ``` 例如，对于字符串s="abcabcbb"，输出的结果为3，因为不包含重复字符的最长子串为"abc"，长度为3。 ### 回答2： 问题描述 给定一个字符串s，找出其中不含有重复字符的最长子串的长度。 解题思路 我们可以通过滑动窗口来解决该问题。定义一个左指针和右指针，将右指针不断右移，每次判断当前右指针指向的字符是否已经在窗口中出现过。如果右指针指向的字符在窗口中出现过，就将左指针向右移动，直到不再有重复字符。在每一步中，通过比较当前的子串长度和之前记录的最长子串的长度来更新最长子串的长度。 具体实现中，我们可以用一个哈希表来记录窗口中出现的每个字符及其出现的位置。每次移动右指针时，先判断当前字符是否已经在哈希表中出现过。如果没有出现过，就将它加入到哈希表中，并继续移动右指针。如果出现过，就更新左指针的位置，将左指针移动到上一个相同字符的下一个位置，并将哈希表中该字符的位置更新为当前的位置。在每一步中，我们记录当前窗口的长度，并比较它和之前记录的最大长度，更新最大长度即可。 实现代码 以下是Python3的实现代码： class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if not s: return 0 left, right = 0, 0 max_len = 0 hash_table = {} while right < len(s): if s[right] in hash_table and hash_table[s[right]] >= left: left = hash_table[s[right]] + 1 hash_table[s[right]] = right right += 1 max_len = max(max_len, right - left) return max_len 时间复杂度 该算法的时间复杂度为$O(n)$，其中$n$是字符串的长度。因为左指针和右指针的移动是单向的，所以每个指针最多移动$n$次。同时，哈希表的查找和更新也是$O(1)$的操作。因此，总的时间复杂度为$O(n)$。 空间复杂度 该算法的空间复杂度为$O(min(n,m))$，其中$n$是字符串的长度，$m$是字符集的大小。哈希表中最多存储$min(n,m)$个键值对，因此空间复杂度为$O(min(n,m))$。 总结 本题可以通过滑动窗口算法来解决，时间复杂度为$O(n)$，空间复杂度为$O(min(n,m))$。滑动窗口算法可以解决字符串中的很多问题，因此掌握该算法对于算法练习和实际工作都非常有用。 ### 回答3： 题目描述 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。 示例 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。 思路分析 首先建立一个哈希表，用来存储字符，字符作为键，下标作为值。 定义两个指针，分别指向子串的开头和结尾。 如果某个字符在哈希表中出现过，并且该字符的下标大于等于start指针指向的下标，则更新start指针为该字符的下标加1。 每次循环更新哈希表和结果res的值，直到结尾指针扫描到字符串的末尾。 最后返回最长子串的长度。 代码实现 def lengthOfLongestSubstring(s: str) -> int: d = {} start = res = 0 # 初始开始指针和最长子串长度为0 for i, ch in enumerate(s): if ch in d and d[ch] >= start: start = d[ch] + 1 d[ch] = i # 哈希表中存储字符和下标 res = max(res, i - start + 1) # 更新最长子串的长度 return res 时间复杂度 O(n) 空间复杂度 O(n) 注意点 1. 子串与子序列的区别：子串要求连续，子序列可以不连续。 2. start指针一定不会往回走，保证了时间复杂度的O(n)。 3. python3中enumerate()函数自动枚举字符串中字符，生成二元组(i, ch)。 4. 函数类型注解可以帮助代码的可读性和维护性。