leetcode中如何查看无重复字符的最长子串
发表于:2024-10-23 作者:千家信息网编辑
千家信息网最后更新 2024年10月23日,这篇文章主要介绍了leetcode中如何查看无重复字符的最长子串,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。题目链接https://
千家信息网最后更新 2024年10月23日leetcode中如何查看无重复字符的最长子串
这篇文章主要介绍了leetcode中如何查看无重复字符的最长子串,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。
题目链接
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
题目描述
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
解题方案
思路
标签:滑动窗口
暴力解法时间复杂度较高,会达到O(n^2),故而采取滑动窗口的方法降低时间复杂度
定义一个map数据结构存储(k,v),其中key值为字符,value值为字符位置+1,加1表示从字符位置后一个才开始不重复
我们定义不重复子串的开始位置为start,结束位置为end
随着end不断遍历向后,会遇到与[start, end]区间内字符相同的情况,此时将字符作为key值,获取其value值,并更新start,此时[start, end]区间内不存在重复字符
无论是否更新start,都会更新其map数据结构和结果ans。
时间复杂度:O(n)
代码
class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(), ans = 0; Mapmap = new HashMap<>(); for (int end = 0, start = 0; end < n; end++) { char alpha = s.charAt(end); if (map.containsKey(alpha)) { start = Math.max(map.get(alpha), start); } ans = Math.max(ans, end - start + 1); map.put(s.charAt(end), end + 1); } return ans; }}
画解
感谢你能够认真阅读完这篇文章,希望小编分享的"leetcode中如何查看无重复字符的最长子串"这篇文章对大家有帮助,同时也希望大家多多支持,关注行业资讯频道,更多相关知识等着你来学习!
字符
最长
长度
位置
篇文章
复杂
复杂度
时间
示例
更新
解释
输入
输出
区间
数据
数据结构
结构
题目
相同
不断
数据库的安全要保护哪些东西
数据库安全各自的含义是什么
生产安全数据库录入
数据库的安全性及管理
数据库安全策略包含哪些
海淀数据库安全审计系统
建立农村房屋安全信息数据库
易用的数据库客户端支持安全管理
连接数据库失败ssl安全错误
数据库的锁怎样保障安全
上海科技大学网络安全考什么
首届网络安全大会的致辞
中国政企网络安全服务上岗证
国内最好的代理服务器
网络安全第三方安全检测
怀柔区品牌软件开发概况
淮安应用软件开发成本预算表
立体仓库三菱数据库
无线网络信号无法连接到服务器
维护网络安全文案
软件开发定价
制作联网数据库
ef从数据库生成实体类
黄河服务器投产
蚌埠通信软件开发定制
可以p动图的手机软件开发
西安商友网络技术有限公司
云服务器上安装软件
诛仙3与服务器的连接已断开
网络安全生态试卷8
有哪些人体数据库
知网数据库能安排的期刊有哪些
淘思数据库
dm数据库中drop加if
数据库电话号码是什么类型的
天下盐商网络技术皋兰县分公司
优化系统数据库
dumi代码部署在服务器上
网络安全可以从事的行业
市场规模数据库模板