赞
踩
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
具体题目信息为:3. 无重复字符的最长子串
软件 | 版本 |
---|---|
JDK | 1.8 |
使用滑动窗口算法即可解决该问题。该算法可以用来解决以下两种类型的问题:
根据问题具体分析使用。本篇博文涉及的题目主要使用哈希表。
class Solution { public int lengthOfLongestSubstring(String s) { int max = 0; char[] list = s.toCharArray(); Map<Integer, Integer> windows = new HashMap<>(); int left = 0,right = 0; int len = 0; while (right < list.length) { int t = list[right]; windows.put(t, windows.getOrDefault(t,0)+1); right ++; while (windows.get(t)>1) { int l = list[left]; windows.put(l, windows.get(l) - 1); left ++; } len = right - left; if (max < len) { max = len; } } if (max < len) { max = len; } return max; } }
需要使用哈希表进行存储,所以空间复杂度为 O(n)
因为只是对字符串进行遍历计算,所以时间复杂度为 O(n)。
多做做算法题,研究一下算法,对自身素养的提升是有很有帮助的!!!
如果我的文章对大家产生了帮忙,可以在文章底部点个赞或者收藏;
如果有好的讨论,可以留言;
如果想继续查看我以后的文章,可以点击关注
可以扫描以下二维码,关注我的公众号:枫夜之求索阁,查看我最新的分享!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。