LeetCode 3: 无重复字符的最长子串 Longest Substring Without Repeating Characters
题目:
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
Given a string, find the length of the longest substring without repeating characters.
示例 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:
class Solution { public int lengthOfLongestSubstring(String s) { char[] chars = s.toCharArray();//转为字符数组 if (chars.length == 0) return 0; HashMap<Character, Integer> 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 数字
欢迎关注微.信.公..众.号: 爱写Bug
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
JavaScript 引擎 V8 执行流程概述
本文主要讲解的是V8的技术,是V8的入门篇,主要目的是了解V8的内部机制,希望对前端,快应用,浏览器,以及nodejs同学有些帮助。这里不涉及到如何编写优秀的前端,只是对JS内部引擎技术的讲解。 一、V8来源 V8的名字来源于汽车的“V型8缸发动机”(V8发动机)。V8发动机主要是美国发展起来,因为马力十足而广为人知。V8引擎的命名是Google向用户展示它是一款强力并且高速的JavaScript引擎。 V8未诞生之前,早期主流的JavaScript引擎是JavaScriptCore引擎。JavaScriptCore是主要服务于Webkit浏览器内核,他们都是由苹果公司开发并开源出来。据说Google是不满意JavaScriptCore和Webkit的开发速度和运行速度,Google另起炉灶开发全新的JavaScript引擎和浏览器内核引擎,所以诞生了V8和Chromium两大引擎,到现在已经是最受欢迎的浏览器相关软件。 二、V8的服务对象 V8是依托Chrome发展起来的,后面确不局限于浏览器内核。发展至今V8应用于很多场景,例如流行的nodejs,weex,快应用,早期的RN。 三...
- 下一篇
Go 开发关键技术指南 | 为什么你要选择 GO?(内含超全知识大图)
作者 |杨成立(忘篱) 阿里巴巴高级技术专家 关注“阿里巴巴云原生”公众号,回复 Go 即可查看清晰知识大图! 导读:从问题本身出发,不局限于 Go 语言,探讨服务器中常常遇到的问题,最后回到 Go 如何解决这些问题,为大家提供 Go 开发的关键技术指南。我们将以系列文章的形式推出《Go 开发的关键技术指南》,共有 4 篇文章,本文为第 1 篇。 Go 开发指南大图 Overview 该指南主要讨论了服务器领域常见的并发问题,也涉及到了工程化相关的问题,还整理了 C 背景程序员对于 Go 的 GC 以及性能的疑问,探讨了 Go 的错误处理和类型系统最佳实践,以及依赖管理的难处、接口设计的正交性,当然也包含我们在服务器开发中对于 Go 实践的总结,有时候也会对一些有趣的问题做深度的挖掘,列出了 Go 重要的事件和资料集合,以及 Go2 的进
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS8编译安装MySQL8.0.19
- CentOS7,CentOS8安装Elasticsearch6.8.6
- CentOS7安装Docker,走上虚拟化容器引擎之路
- Eclipse初始化配置,告别卡顿、闪退、编译时间过长
- Mario游戏-低调大师作品
- 2048小游戏-低调大师作品
- SpringBoot2初体验,简单认识spring boot2并且搭建基础工程
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- SpringBoot2整合Thymeleaf,官方推荐html解决方案