您好,登录后才能下订单哦!
本篇文章为大家展示了使用LeetCode怎么实现无重复字符的最长子串,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3
示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
示例 4:
输入: s = "" 输出: 0
0 <= s.length <= 5 * 104 s 由英文字母、数字、符号和空格组成
检查重复字符串的思路有哪些?
两次遍历循环字符串
存入之前判断Set中是否已经存在字符串
计算最新的结果长度,并且将当前字符串存入到Set
中
每当第二次循环完成之后,清空Set,防止影响下一个第一层循环的数据
有则BREAK
,进入下一个外层循环
第一层循环记录头部信息
第二层循环用来滑动数据
将第二层数据存入到Set
中
class Solution { public int lengthOfLongestSubstring(String s) { int res = 0 ; Set<Character> set = new HashSet<>(); for(int i = 0 ; i < s.length();i++){ for(int j = i ; j < s.length() ; j++){ if(set.contains(s.charAt(j))){ break; } if(j-i+1 > res){ res = j-i+1; } set.add(s.charAt(j)); } set.clear(); } return res; } }
时间复杂度:O(N^2)
,N
为S
的长度
执行用时:99
ms, 在所有 Java 提交中击败了12.37
%的用户
内存消耗:38.7
MB, 在所有 Java 提交中击败了39.62
%的用户
双指针
,又名滑动窗口
,其实就是一个队列
,比如例题中的 abcabcbb
,进入这个队列(窗口)为 abc
满足题目要求,当再进入 a,队列变成了 abca,这时候不满足要求。所以,我们要移动这个队列!
当前Left为0,Right为2,整体的结果最大长度为3,缓存cache中已经有了数据{A:0,B:1,C:2}
当再次遇到A
时,缓存cache
中已经存在了A
字符串,我们需要比较【当前A
在缓存中的位置】,与【当前Left
的值】,如果Left
的值小于等于A
在缓存中的位置,那么我们需要调整Left
的值为(A
在缓存中的位置 + 1
),这么做主要是为了Left坐标始终处于最新的重合点的位置的后面一位
,组成新的不重合的长度
ABCAB
跟上面同理,当遇到B
时,缓存中已经存在了B
字符串,需要比较【当前B
在缓存中的位置】,与【当前Left
的值】,如果Left
的值小于等于``B
在缓存中的位置,那么久需要调整Left
的值为(B
在缓存中的位置+1
),最终是为了Left坐标始终处于最新的重合点(B
)的位置的后面一位
,组成新的不重合的长度
class Solution { public int lengthOfLongestSubstring(String s) { int length = s.length(); if(length == 0){ return 0; } int res = 0 ; //快指针 int right = 0 ; //慢指针 int left = 0 ; //索引,空间换时间 Map<Character,Integer> map = new HashMap<>(); for(;right<length;right++){ Character c = s.charAt(right); if(map.containsKey(c)){ //更新left if( map.get(c) >= left){ left = map.get(c)+1; } } //更新结果res if((right-left+1)>res){ res = (right-left+1); } //更新c的位置 map.put(c,right); } return res ; } }
时间复杂度:O(N)
,N
为字符串长度
执行用时:7
ms, 在所有 Java 提交中击败了79.24
%的用户
内存消耗:38.8
MB, 在所有 Java 提交中击败了28.63
%的用户
上述内容就是使用LeetCode怎么实现无重复字符的最长子串,你们学到知识或技能了吗?如果还想学到更多技能或者丰富自己的知识储备,欢迎关注亿速云行业资讯频道。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。