开发者社区> 千锋Python讲堂> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

Java/Python:无重复字符的最长子串讲解

简介: Java/Python:无重复字符的最长子串讲解
+关注继续查看

题目:

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

示例 1:

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

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

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

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

Java:

class Solution { public int lengthOfLongestSubstring(String s) { char[] chars = s.toCharArray();//转为字符数组 if (chars.length == 0) return 0; HashMap map = new HashMap<>();//建立哈希映射 int size = s.length(), count = 0, i = 0; for (int j = 0; j < size; j++) {//遍历字符 if (map.containsKey(chars[j]))//如果映射中存在该字符 i = Math.max(map.get(chars[j]), i);//更新滑动窗口的左边界 i count = Math.max(count, j - i);//更新 count 为最大值 map.put(chars[j], j + 1);//更新映射中该字符映射的 Value 值为当前位置加一 } return count + 1;//返回最大累加总数, 需要加 1 }}
Python:

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

Java:

class Solution { public int lengthOfLongestSubstring(String s) { char[] chars = s.toCharArray(); if (chars.length == 0) return 0; int[] index = new int[128];//建立长度为 128 位的 ASCII 码字符映射表 int size = s.length(), count = 0, i = 0; for (int j = 0; j < size; j++) {//遍历字符 i = Math.max(index[chars[j]], i);//更新滑动窗口的左边界 i count = Math.max(count, j - i);//更新 count 为最大值 index[chars[j]] = j + 1;//更新映射中该字符所在元素值为当前位置加一 } return count + 1;//返回最大累加总数, 需要加 1 }}
Python:

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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Python编程:Python2.7环境下的中文文件读写
Python编程:Python2.7环境下的中文文件读写
0 0
Python编程:实现tail-n查看日志文件
Python编程:实现tail-n查看日志文件
0 0
Python编程:pickleDB库Redis的简易替代
pickleDB 是一个轻量简单的 key-value 存储器,操作和redis 很类似 可以作为一个不错的工具
0 0
Python编程:six库兼容Python 2 和 Python 3
six 它是一个专门用来兼容 Python 2 和 Python 3 的库
0 0
Python编程:使用cachy缓存数据
Python编程:使用cachy缓存数据
0 0
python编程之数字和字符串类型
python编程之数字和字符串类型
0 0
PennyLane | 用于量子计算机可微分编程的跨平台Python库
PennyLane | 用于量子计算机可微分编程的跨平台Python库
0 0
python文档:开始进入编程(在前面的基础上)
python文档:开始进入编程(在前面的基础上)
0 0
2019年上半年收集到的人工智能Python编程干货文章
2019年上半年收集到的人工智能Python编程干货文章
0 0
+关注
千锋Python讲堂
Python忠实粉!从业Python已有6年!希望在这里跟大家一起分享我的经验和同伴交流!
文章
问答
文章排行榜
最热
最新
相关电子书
更多
Python第五讲——关于爬虫如何做js逆向的思路
立即下载
Python系列直播第一讲——Python中的一切皆对象
立即下载
Python 脚本速查手册
立即下载