python连续重复字符_Java/Python：无重复字符的最长子串讲解

题目:

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

示例 1:

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

示例 2:

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

示例 3:

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

解题思路:

• 暴力求解, 时间复杂度为 O(n^3), 因为要对所有字符遍历, 对子串遍历确认是否有重复字符, pass
• 滑动窗口, 维护一个索引 [i,j) 的滑动窗口, 对已存在的字符 i&＃39; 直接更新滑动窗口 [i&＃39;,j), 你需要保留每一个字符值及其索引, 即由字符映射索引位置哈希映射: Key 为字符值, Value 为索引位置字符映射: ASCII 码共 128 个字符, 维护一个长度为 128 的整型数组,数组索引值映射 128 个字符,存储元素值为字符位置

哈希映射:

Java:

class Solution { public int lengthOfLongestSubstring(String s) { char[] chars &＃61; s.toCharArray();//转为字符数组 if (chars.length &＃61;&＃61; 0) return 0; HashMap map &＃61; new HashMap<>();//建立哈希映射 int size &＃61; s.length(), count &＃61; 0, i &＃61; 0; for (int j &＃61; 0; j

Python:

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if not s: return 0 hash_map &＃61; dict() # 建立字典 size &＃61; len(s) i, count &＃61; 0, 0 for j, c in enumerate(s): # 枚举字符 if c in hash_map: # 如果映射中存在该字符 i &＃61; max(i, hash_map[c]) # 更新滑动窗口的左边界 i count &＃61; max(count, j-i) # 更新 count 为最大值 hash_map[c] &＃61; j&＃43;1 # 更新映射中该字符映射的 Value 值为当前位置加一 return count&＃43;1 # 返回最大累加总数, 需要加 1

字符映射:

Java:

class Solution { public int lengthOfLongestSubstring(String s) { char[] chars &＃61; s.toCharArray(); if (chars.length &＃61;&＃61; 0) return 0; int[] index &＃61; new int[128];//建立长度为 128 位的 ASCII 码字符映射表 int size &＃61; s.length(), count &＃61; 0, i &＃61; 0; for (int j &＃61; 0; j

Python:

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if not s: return 0 size &＃61; len(s) i, count &＃61; 0, 0 index &＃61; [0]*128 # 建立长度为 128 位的 ASCII 码字符映射表 for j, c in enumerate(s): # 枚举字符 i &＃61; max(i, index[ord(c)]) # 更新滑动窗口的左边界 i count &＃61; max(count, j-i) # 更新 count 为最大值 index[ord(c)] &＃61; j&＃43;1 # 更新映射中该字符所在元素值为当前位置加一 return count&＃43;1 # 返回最大累加总数, 需要加 1

因为 Python 没有字符概念, 需要 ord() 函数转为 ASCII 数字