题目描述
给定一个字符串
s
,请你找出其中不含有重复字符的 最长子串
的长度。
示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是"abc"
,所以其长度为 3。示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是"b"
,所以其长度为 1。示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是"wke"
,所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke"
是一个子序列,不是子串。提示:
0 <= s.length <= 5 * 104
s
由英文字母、数字、符号和空格组成
思路
这道题主要用到思路是:滑动窗口
什么是滑动窗口?
其实就是一个队列,比如例题中的 abcabcbb,进入这个队列(窗口)为 abc 满足题目要求,当再进入 a,队列变成了 abca,这时候不满足要求。所以,我们要移动这个队列!
如何移动?
我们只要把队列的左边的元素移出就行了,直到满足题目要求!
一直维持这样的队列,找出队列出现最长的长度时候,求出解!
解题步骤
需要定义指针指向滑动窗口左右
定义一个set来保存当前不重复元素集合
循环遍历字符串,条件是没有循环到末尾
当set中没有包含该字符时,就将该字符添加到set中,同时右指针向右移动
当set中已经包含了字符时,就先将set中重复字符移除,同时左指针向右移动
然后获取当前最长的长度,就是当前set长度和当前最长长度中取最大值
如abcabcbb,一开始abc,set中都不包含,添加进set,right从0移动到2
继续移动right=3,set= abc时,如果再添加a,就需要将set中a移除,变成bc,left从0变成1
然后下次循环,set中变成bc,此时right=3,a又不包含在内了,添加进set,变成是bca
依次进行下去
然后计算最长长度即可
代码
class Solution {
public static int lengthOfLongestSubstring(String s) {
int left =0;//左指针
int right=0;//右指针
int maxLen=0;//最大长度
//set集合保存不重复字符
Set<Character> set = new HashSet<>();
while(right<s.length()){
//当set不包含重复字符时,添加到set,右指针右移动
if(!set.contains(s.charAt(right))){
set.add(s.charAt(right));
right++;
}else{
//包含,先将左指针指向的位置元素删除,然后左指针移动
set.remove(s.charAt(left));
left++;
}
//计算最大长度
maxLen= Math.max(maxLen,set.size());
}
return maxLen;
}
}
标签:子串,字符,set,队列,最长,长度,LeetCode
From: https://blog.csdn.net/lingxiyizhi_ljx/article/details/141155506